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);
}
