102. 二叉树的层序遍历

/*** 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 List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>>  result = new ArrayList<>();if(root == null){return result;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){// 获取当前层级节点的数量int size = queue.size();List<Integer> list = new ArrayList<>();for(int i = 0; i < size; i++ ){TreeNode node = queue.poll();list.add(node.val);if(node.left != null){queue.offer(node.left);}if(node.right != null){queue.offer(node.right);}}result.add(list);}return result;}
}

same with

学会二叉树的层序遍历，可以一口气打完以下十题：

• 102.二叉树的层序遍历
• 107.二叉树的层次遍历II
• 199.二叉树的右视图
• 637.二叉树的层平均值
• 429.N叉树的层序遍历
• 515.在每个树行中找最大值
• 116.填充每个节点的下一个右侧节点指针
• 117.填充每个节点的下一个右侧节点指针II
• 104.二叉树的最大深度
• 111.二叉树的最小深度

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) {if(root == null){return null;}invertTree(root.left);invertTree(root.right);swapChildren(root);return root;}private void swapChildren(TreeNode root){TreeNode temp = root.left;root.left = root.right;root.right = temp;}
}

首先递归地翻转了当前节点的左子树和右子树，然后在返回到当前节点时，交换了它的左子树和右子树。在翻转子树之后再交换当前节点的左右子树

把交换左右子树的代码放在了一个单独的方法中，这使得代码更易于理解和维护。

前序遍历和后序遍历都可以用来解决这个问题，

但中序遍历不行。这是因为在中序遍历中，我们需要先处理左子树，然后处理当前节点，最后处理右子树，如果在处理当前节点时交换左右子树，那么处理右子树时实际上处理的是原来的左子树，所以不能得到正确的结果。

在时间复杂度和空间复杂度方面，是O(n)和O(h)，其中n是二叉树中的节点数，h是二叉树的高度。

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) {return root == null || isSymmetricHelper(root.left, root.right);}private boolean isSymmetricHelper(TreeNode left, TreeNode right) {if (left == null || right == null) {return left == right;}if (left.val != right.val) {return false;}return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left);}
}

首先检查根节点是否为null，如果是，那么树就是对称的。如果根节点不为null，那么就调用辅助方法 isSymmetricHelper 来检查根节点的左右子树是否对称。

isSymmetricHelper 方法首先检查传入的两个节点是否为null，如果其中一个为null，那么只有当另一个节点也为null时，这两个节点才对称。

如果两个节点都不为null，那么就比较他们的值是否相等，如果不相等，那么这两个节点就不对称。

如果两个节点的值相等，那么就递归地比较这两个节点的左右子树是否对称。因为对于一个对称的二叉树，任何两个对称的节点的左子树都和另一个节点的右子树对称，所以我们递归地调用 isSymmetricHelper 来比较这两个节点的左右子树。

这个方法的时间复杂度是O(n)，其中n是二叉树中的节点数，因为我们需要遍历树中的每一个节点。空间复杂度是O(h)，其中h是二叉树的高度，这是因为在递归的过程中需要使用到栈空间，最大深度就是树的高度。