* 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) {
// Queue<TreeNode> queue = new LinkedList<>();
// int size = queue.size();
// if(root != null){
// queue.offer(root);
// size = queue.size();
// }
// while(!queue.isEmpty()){
// while(size > 0){
// TreeNode cur = queue.poll();
// if(cur.left != null){
// queue.offer(cur.left);
// }
// if(cur.right != null){
// queue.offer(cur.right);
// }
// swapChildren(cur);
// size--;
// }
// size = queue.size();
// }
// return root;
// }
// public void swapChildren(TreeNode cur){
// TreeNode temp = cur.left;
// cur.left = cur.right;
// cur.right = temp;
// }
// 方法二：递归法，后序
// public TreeNode invertTree(TreeNode root) {
// if(root == null){
// return root;
// }
// invertTree(root.left);
// invertTree(root.right);
// swapChildren(root);
// return root;
// }
// public void swapChildren(TreeNode cur){
// TreeNode temp = cur.left;
// cur.left = cur.right;
// cur.right = temp;
// }
// 方法三：迭代法：中序，统一风格
public TreeNode invertTree(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
if(root != null){
stack.push(root);
}
while(!stack.isEmpty()){
if(stack.peek() != null){
TreeNode cur = stack.pop();
if(cur.right != null)
stack.push(cur.right);
if(cur.left != null)
stack.push(cur.left);
stack.push(cur);
stack.push(null);
swapChildren(cur);
}else{
stack.pop();
stack.pop();
}
}
return root;
}
public void swapChildren(TreeNode cur){
TreeNode temp = cur.left;
cur.left = cur.right;
cur.right = temp;
}
}
590、N 叉树的后序遍历
101、对称二叉树
class Solution {
// 方法一：递归，后序遍历
// public boolean isSymmetric(TreeNode root) {
// return compare(root.left, root.right);
// }
// public boolean compare(TreeNode left, TreeNode right){
// if(left == null && right != null){
// return false;
// }
// if(right == null && left != null){
// return false;
// }
// if(right == null && left == null){
// return true;
// }
// if(left.val != right.val){
// return false;
// }
// boolean resultLeft = compare(left.left, right.right);
// boolean resultRight = compare(left.right, right.left);
// return resultLeft && resultRight;
// }
// 方法二：迭代
public boolean isSymmetric(TreeNode root) {
Deque<TreeNode> deque = new LinkedList<>();
deque.offerFirst(root.left);
deque.offerLast(root.right);
while(!deque.isEmpty()){
TreeNode left = deque.pollFirst();
TreeNode right = deque.pollLast();
if(left == null && right == null){
continue;
}
if(left == null && right != null){
return false;
}
if(left != null && right == null){
return false;
}
if(left.val != right.val){
return false;
}
deque.offerFirst(left.left);
deque.offerFirst(left.right);
deque.offerLast(right.right);
deque.offerLast(right.left);
}
return true;
}
}
589、N 叉树的前序遍历
class Solution {
// 方法一：递归
// public List<Integer> resultList = new ArrayList<>();
// public List<Integer> preorder(Node root) {
// if(root == null){
// return resultList;
// }
// resultList.add(root.val);
// for(Node node : root.children){
// preorder(node);
// }
// return resultList;
// }
// 方法二：迭代，统一风格
public List<Integer> pr