方法：遞歸

思路：

自下而上地統計。(相當于后序遍歷)

• 如果node是null，返回0
• 遍歷node.left和node.right
• 取較大者，加一，返回給上一層。（為什么這里要“+1”，因為要告訴上一層“我這里有一層”，這個“一層”就是“+1”的效果。）

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);return Math.max(leftDepth, rightDepth) + 1;}
}

方法：遞歸

思路：

自頂向下地統計。（相當于前序遍歷）

class Solution {private int res;public int maxDepth(TreeNode root) {dfs(root, 0);return res;}private void dfs(TreeNode node, int depth) {if (node == null) {return;}depth++;res = Math.max(res, depth);dfs(node.left, depth);dfs(node.right, depth);}
}

方法：迭代

思路：

層序遍歷。有多少層就有深。

• 利用queue來記錄每層的節點。
• 遍歷完一層之后，記錄size。
• 下一層遍歷queue中的size個節點。

class Solution {public int maxDepth(TreeNode root) {if (root == null) {return 0;}Deque<TreeNode> que = new ArrayDeque<>();int depth = 0;que.offer(root);while (!que.isEmpty()) {depth++;int size = que.size();while (size-->0) {TreeNode cur = que.poll();if (cur.left != null) {que.offer(cur.left);}if (cur.right != null) {que.offer(cur.right);}}}return depth;}
}

思路：

自頂向下。

先交換左右子樹，再進入下一層。遞歸解決。

class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}// 先交換左右子樹，再進入下一層TreeNode temp = root.left;root.left = root.right;root.right = temp;invertTree(root.left);invertTree(root.right);return root;}
}

思路：

自底向上。

先遞歸到最下層，交換左右節點。再返回給上層。

class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);root.left = right;root.right = left;return root;}
}

思路：

先反轉左子樹，再和右子樹比較是否相等。

class Solution {public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}// 先反轉左子樹invertTree(root.left);// 再和右子樹比較是否相等return isSameTree(root.left, root.right);}// 226. 翻轉二叉樹private TreeNode invertTree(TreeNode root) {if (root == null) {return null;}TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);root.left = right;root.right = left;return root;}// 100. 相同的樹private boolean isSameTree(TreeNode p, TreeNode q) {if (p == null || q == null) {return p == q;}return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}
}

思路：

直接改造isSameTree方法。

要判斷三個條件：

1，該節點值是否相等。

2，left的左子樹和right的右子樹是否相等。

3，left的右子樹和right的左子樹是否相等，

class Solution {public boolean isSymmetric(TreeNode root) {return isSameTree(root.left, root.right);}// 在【100. 相同的樹】的基礎上稍加改動private boolean isSameTree(TreeNode p, TreeNode q) {if (p == null || q == null) {return p == q;}return p.val == q.val && isSameTree(p.left, q.right) && isSameTree(p.right, q.left);}
}