代码随想录四刷day14

本文主要是介绍代码随想录四刷day14，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

前言
一、力扣226. 翻转二叉树
二、力扣589. N 叉树的前序遍历
三、力扣590. N 叉树的后序遍历
四、力扣101. 对称二叉树

前言

迭代法中我们使用了队列，需要注意的是这不是层序遍历，而且仅仅通过一个容器来成对的存放我们要比较的元素，知道这一本质之后就发现，用队列，用栈，甚至用数组，都是可以的。

一、力扣226. 翻转二叉树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode invertTree(TreeNode root) {return preOrder(root);}public TreeNode preOrder(TreeNode root){if(root == null){return null;}TreeNode t = root.left;root.left = root.right;root.right = t;preOrder(root.left);preOrder(root.right);return root;}
}

二、力扣589. N 叉树的前序遍历

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {List<Integer> res = new ArrayList<>();public List<Integer> preorder(Node root) {preOrder(root);return res;}public void preOrder(Node root){if(root == null){return;}res.add(root.val);for(Node node : root.children){preOrder(node);}}
}

迭代

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {List<Integer> res = new ArrayList<>();Deque<Node> deq = new LinkedList<>();public List<Integer> preorder(Node root) {if(root == null){return res;}deq.offerLast(root);while(!deq.isEmpty()){Node p = deq.pollLast();res.add(p.val);for(int i = p.children.size()-1; i >= 0; i --){deq.offerLast(p.children.get(i));}}return res;}
}

三、力扣590. N 叉树的后序遍历

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {List<Integer> res = new ArrayList<>();public List<Integer> postorder(Node root) {fun(root);return res;}public void fun(Node root){if(root == null){return;}for(Node node : root.children){fun(node);}res.add(root.val);}
}

迭代

/*
// Definition for a Node.
class Node {public int val;public List<Node> children;public Node() {}public Node(int _val) {val = _val;}public Node(int _val, List<Node> _children) {val = _val;children = _children;}
};
*/class Solution {List<Integer> res = new ArrayList<>();Deque<Node> deq = new LinkedList<>();public List<Integer> postorder(Node root) {if(root == null){return res;}deq.offerLast(root);while(!deq.isEmpty()){Node p = deq.pollLast();res.add(p.val);for(Node node : p.children){deq.offerLast(node);}}Collections.reverse(res);return res;}}

四、力扣101. 对称二叉树

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {if(root == null){return true;}return fun(root.left, root.right);}public boolean fun(TreeNode l, TreeNode r){if(l == null && r == null){return true;}else if(l != null && r != null){if(l.val != r.val){return false;}boolean b1 = fun(l.left, r.right);boolean b2 = fun(l.right, r.left);return b1 && b2;}else{return false;}}
}

层序遍历

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {if(root == null){return true;}Deque<TreeNode> deq = new LinkedList<>();deq.offerLast(root.left);deq.offerLast(root.right);while(!deq.isEmpty()){TreeNode l = deq.pollFirst();TreeNode r = deq.pollFirst();if(l == null && r == null){continue;}if(l == null && r != null || l != null && r == null){return false;}if(l.val != r.val){return false;}deq.offerLast(l.left);deq.offerLast(r.right);deq.offerLast(l.right);deq.offerLast(r.left);}return true;}
}