1.相同的树（100-易）
题目描述：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例：
输入：p = [1,2,3], q = [1,2,3] 输出：true
思路：如果两棵树相同，其子树也一定相同：树的结构和数值相同。
代码实现：
public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p == null || q == null) { return false; } if (p.val != q.val) { return false; } return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); }
延伸(T572/剑指26)：给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。
思路：判断一棵树是否为另一棵树的子树。这样就是判断t的头结点与s所有子节点比较是否是相同的树。
代码实现：
public boolean isSubtree(TreeNode s, TreeNode t) { if (s == null) { return false; } return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t); } private boolean isSubtreeWithRoot(TreeNode s, TreeNode t) { if (s == null && t == null) { return true; } if (s == null || t == null) { return false; } if (s.val != t.val) { return false; } return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right); }
2.对称二叉树（101-易）
题目描述：给定一个二叉树，检查它是否是镜像对称的。要求：迭代和递归。
示例：
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 / \ 2 2 / \ / \ 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1 / \ 2 2 \ \ 3 3
思路：
- 递归：与上题相同，只不过我们递归的逻辑改变（不是两个子树的对应位置比较）
- 迭代：关键是如何入队，我们每次都能取出两个节点，一个代表左子树，另一个代表右子树。
代码实现：
// 递归 public boolean isSymmetric(TreeNode root) { if (root == null) { return true; } return dfs(root.left, root.right); } public boolean dfs(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p == null || q == null) { return false; } if (p.val != q.val) { return false; } return dfs(p.left, q.right) && dfs(p.right, q.left); } // 迭代 public boolean isSymmetric(TreeNode root) { if (root == null || (root.left == null && root.right == null)) { return true; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root.left); queue.add(root.right); while (!queue.isEmpty()) { TreeNode left = queue.poll(); TreeNode right = queue.poll(); if (left == null && right == null) { continue; } if (left == null || right == null) { return false; } if (left.val != right.val) { return false; } queue.add(left.left); queue.add(right.right); queue.add(left.right); queue.add(right.left); } return true; }
2.翻转二叉树/镜像（226-易/剑指27）
示例：
输入： 4 / \ 2 7 / \ / \ 1 3 6 9 输出： 4 / \ 7 2 / \ / \ 9 6 3 1
思路：递归与迭代实现。
- 递归：进行递归翻转时，比如我们先翻转左子树，我们就要记录一下这个节点，方便翻转右子树。
- 迭代：每次从队列中拿出一个节点，交换这两个节点的左右子树。
代码实现：
// 递归 public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } TreeNode left = root.left; root.left = invertTree(root.right); root.right = invertTree(left); return root; } public boolean dfs(TreeNode p, TreeNode q) { if (p == null && q == null) { return true; } if (p == null || q == null) { return false; } if (p.val != q.val) { return false; } return dfs(p.left, q.right) && dfs(p.right, q.left); } // 迭代 public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { TreeNode cur = queue.poll(); TreeNode left = cur.left; cur.left = cur.right; cur.right = left; if (cur.left != null) { queue.add(cur.left); } if (cur.right != null) { queue.add(cur.right); } } return root; }
拓展（T951）：判断两树是否翻转等价。我们可以为二叉树 T 定义一个翻转操作，如下所示：选择任意节点，然后交换它的左子树和右子树。
只要经过一定次数的翻转操作后，能使 X 等于 Y，我们就称二叉树 X 翻转等价于二叉树 Y。编写一个判断两个二叉树是否是翻转等价的函数。这些树由根节点 root1 和 root2 给出。
- 递归思路：本题是子树和翻转树的结合版，不满足子树直接返回false，否则，我们递归两种情况：子树或翻转树（因为我们不知道究竟是哪几个节点翻转了）
代码实现：
public boolean flipEquiv(TreeNode root1, TreeNode root2) { if (root1 == null && root2 == null) { return true; } if (root1 == null || root2 == null || root1.val != root2.val) { return false; } return flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right) || flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left); }
3.验证二叉搜索树（98-中）
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
思路：二叉搜索树中序（左中有）升序，中序遍历二叉搜索树。这里有一个技巧就是设置pre变量。
代码实现：
long pre = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if (root == null) { return true; } if (!isValidBST(root.left)) { return false; } //访问当前节点，当前节点小于或者等于中序遍历的上一个节点不满足规则 if (root.val <= pre) { return false; } pre = root.val; return isValidBST(root.right); }
4.二叉搜索树的查找、插入与删除操作
题目描述：二叉搜索树中给定值的查找（T700）、插入（T701）和删除（T405）。保证结果任然是二叉搜索树。
查找：递归与迭代实现，利用二叉搜索树的性质。
- 注意：我们要返回值等于val的节点（子树），其余的都不要！！所以，对于遍历过程中，我们是直接返回即可，不需要像插入和删除一样进行连接
代码实现：
查找二叉搜索树给定值节点：
public TreeNode searchBST(TreeNode root, int val) { if (root == null || val == root.val) return root; return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val); }
插入：递归与迭代实现，利用二叉搜索树的性质。
- 递归函数终止条件，root == null， 创建节点插入（这种思路保证：插入节点一定在叶子节点）
- 迭代实现：与递归实现相同，定义一个cur指针遍历二叉搜索树，主要还是依靠bst树的性质。
代码实现：
// 递归 public TreeNode insertIntoBST(TreeNode root, int val) { if (root == null) { return new TreeNode(val); } if (val > root.val) { root.right = insertIntoBST(root.right, val); } else if (val < root.val) { root.left = insertIntoBST(root.left, val); } return root; } // 迭代 public TreeNode insertIntoBST(TreeNode root, int val) { TreeNode node = new TreeNode(val); if (root == null) { return node; } TreeNode cur = root; while (cur != null) { if (val > cur.val) { if (cur.right == null) { cur.right = node; break; } cur = cur.right; } else { if (cur.left == null) { cur.left = node; break; } cur = cur.left; } } return root; }
删除：根据二叉搜索树的性质，我们可以通过节点值大小，确定待删除节点的位置。一般情况，如果删除当前节点，分两种情况：
- 无左或者右子节点，删除该节点，对应的子树顶上
- 左右子节点都有，其左子树转移到其右子树的最左节点的子树上，然后右子树顶替其位置，由此删除了该节点。
注意：
- 递归函数返回的是删除该节点后的，顶替上来的根节点。
- 寻找左右子树的过程，我们没有删除，不能返回！
代码实现：
public TreeNode deleteNode(TreeNode root, int key) { if (root == null) { return null; } if (key > root.val) { root.right = deleteNode(root.right, key); } else if (key < root.val) { root.left = deleteNode(root.left, key); } else { if (root.left == null) { return root.right; } if (root.right == null) { return root.left; } TreeNode node = root.right; // 寻找其右子树的最左节点 while (node.left != null) { node = node.left; } node.left = root.left; root = root.right; } return root; }
5.二叉搜索树中第K小的元素（230-中）
给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。
思路：定义一个count函数记录节点个数，根据二叉搜索树的性质，判断目标节点值。
代码实现：
public int kthSmallest(TreeNode root, int k) { int leftCount = count(root.left); if (leftCount == k - 1) { return root.val; } return leftCount < k - 1 ? kthSmallest(root.right, k - leftCount - 1) : kthSmallest(root.left, k); } private int count(TreeNode node) { if (node == null) { return 0; } return count(node.left) + count(node.right) + 1; }
延伸：剑指54，第k大的元素。同理
代码实现：
public int kthLargest(TreeNode root, int k) { int rightCount = count(root.right); if (rightCount == k - 1) { return root.val; } return rightCount < k - 1 ? kthLargest(root.left, k - rightCount - 1) : kthLargest(root.right, k); } private int count(TreeNode node) { if (node == null) { return 0; } return count(node.left) + count(node.right) + 1; }
6.左叶子之和（404-易）
计算给定二叉树的所有左叶子之和。 示例： 3 / \ 9 20 / \ 15 7 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
有两种递归的思路：
- 前序遍历：比较好理解的是利用前序遍历（判断当前节点是否为左叶子节点）。
- 自上向下递归：如果当前节点左子节点累积和（不要忘记递归右子树），再递归左右子树
// 前序遍历 private int ans = 0;; public int sumOfLeftLeaves(TreeNode root) { if (root == null) { return 0; } inorder(root, false); return ans; } private void inorder(TreeNode node, boolean isLeft) { if (node == null) { return; } if (node.left == null && node.right == null && isLeft) { ans += node.val; } inorder(node.left, true); inorder(node.right, false); } // 自上向下递归 public int sumOfLeftLeaves(TreeNode root) { if (root == null) { return 0; } if (isLeaf(root.left)) { return root.left.val + sumOfLeftLeaves(root.right); } return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right); } private boolean isLeaf(TreeNode node) { if (node == null) { return false; } return node.left == null && node.right == null; }
7.二叉搜索树的最近公共祖先（235-易）
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。注：一个节点本身也可以是自己的祖先。
思路：利用二叉搜索树的性质，本质是一个分治的过程，直接递归求解。注：一个节点本身也可以是自己的祖先。
迭代求解：迭代我们如何利用二叉搜索树性质呢，利用节点值的差值。如果在左子树或者右子树，那么当前节点值与这两个节点的差值乘积一定为正(即两个节点在同侧)。
// 递归 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root.val > p.val && root.val > q.val) { return lowestCommonAncestor(root.left, p, q); } if (root.val < p.val && root.val < q.val) { return lowestCommonAncestor(root.right, p, q); } return root; } // 迭代 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { TreeNode cur = root; while ((cur.val - p.val) * (cur.val - q.val) > 0) { cur = cur.val > p.val ? cur.left : cur.right; } return cur; }
进阶：二叉树的最近公共祖先（T236）
递归和迭代求解：
- 递归：作为上一题的进阶（上题我们通过比较较节点值大小确定左右子树的），这里我们任然需要处理这个问题。类似后续遍历，先遍历在左右子树的最近公共祖先，再判断当前位置。主要分为三种情况，见代码。
- 迭代（比较巧妙）：对于两个节点的公共祖先，root一定是他们的公共祖先但不是最近的，最近的应该是最开始的分叉节点。
所以，我们可以倒序其中的一条路径，然后看当前路径在不在另一条路径上，当第一次出现这个节点就是最近的公共祖先。
（1）倒序一条路径的话：使用hashmap存储这个节点的父节点
（2）我们要查看两条路径有没有重合：使用hashset存储其中一个路径的节点值，方便判断
（3）如何找到这两个节点呢：我们使用一个栈结构，从root节点开始查找，当hashmap出现这两个节点的时候，停止，开始倒序。
代码实现：
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) { return root; } TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if (left != null && right != null) { return root; } return left == null ? right : left; } // 迭代 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { Deque<TreeNode> stack = new LinkedList<>(); Map<TreeNode, TreeNode> parents = new HashMap<>(); stack.push(root); parents.put(root, null); while (!parents.containsKey(p) || !parents.containsKey(q)) { TreeNode cur = stack.pop(); if (cur.left != null) { stack.push(cur.left); parents.put(cur.left, cur); } if (cur.right != null) { stack.push(cur.right); parents.put(cur.right, cur); } } HashSet<TreeNode> path = new HashSet<>(); while (p != null) { path.add(p); p = parents.get(p); } while (q != null) { if (path.contains(q)) { break; } q = parents.get(q); } return q; }
8.拓展（T1026）节点与其祖先节点的最大差值
给定二叉树的根节点 root，找出存在于 不同 节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。返回这个最大值。
（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）
输入：root = [8,3,10,1,6,null,14,null,null,4,7,13] 输出：7 解释： 我们有大量的节点与其祖先的差值，其中一些如下： |8 - 3| = 5 |3 - 7| = 4 |8 - 1| = 7 |10 - 13| = 3 在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。
思路：
- 题目解读：不管谁是谁的祖先，一个节点的最大差值，本质就是求解一条路径上的最大值与最小值的差值。
注意：路径的端点为任意节点！
代码实现：
private int ans = 0; public int maxAncestorDiff(TreeNode root) { if (root == null) { return 0; } inorder(root, root.val, root.val); return ans; } private void inorder(TreeNode root, int max, int min) { if (root == null) { return; } min = Math.min(min, root.val); max = Math.max(max, root.val); ans = Math.max(Math.abs(max - min), ans); min = Math.min(min, root.val); max = Math.max(max, root.val); inorder(root.left, max, min); inorder(root.right, max, min); }
