二叉树的基础知识参考：算法分析之二叉树，二叉树的递归和迭代遍历方法参考：算法分析之二叉树遍历。
- 一、二叉树的解题方法
- 1. 递归法
- 2. 迭代法
- 二、leetcode例题讲解二叉树问题
- 1. 二叉树的属性问题
- 101. 对称二叉树
- 100. 相同的树
- 104. 二叉树的最大深度
- 111. 二叉树的最小深度
- 222. 完全二叉树的节点个数
- 110. 平衡二叉树
- 257. 二叉树的所有路径
- 404. 左叶子之和
- 513. 找树左下角的值
- 112. 路径总和
- 2. 二叉树的修改和改造问题
- 226. 翻转二叉树
- 106. 从中序与后序遍历序列构造二叉树
- 105. 从前序与中序遍历序列构造二叉树
- 654. 最大二叉树
- 617. 合并二叉树
- 3. 二叉树的公共祖先问题
- 236. 二叉树的最近公共祖先
- 三、leetcode例题讲解二叉搜索树问题
- 1. 二叉搜索树的属性问题
- 700. 二叉搜索树中的搜索
- 98. 验证二叉搜索树
- 530. 二叉搜索树的最小绝对差
- 501. 二叉搜索树中的众数
- 538. 把二叉搜索树转换为累加树
- 2. 二叉搜索树的修改和改造问题
- 701. 二叉搜索树中的插入操作
- 450. 删除二叉搜索树中的节点
- 669. 修剪二叉搜索树
- 108. 将有序数组转换为二叉搜索树
- 3. 二叉搜索树的公共祖先问题
- 235. 二叉搜索树的最近公共祖先
二叉树问题中，递归是非常好用的解题方法。
每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！
-
确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
-
确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
-
确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
遇到二叉树的算法首先可以考虑递归实现，分别递归左右子树。
2. 迭代法递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
因此，能用递归解决的问题，也可以使用栈和队列迭代实现。
使用前中后序遍历方法的话借助栈，使用层序遍历的话，使用队列。
模板请参考：算法分析之二叉树遍历。
二、leetcode例题讲解二叉树问题 1. 二叉树的属性问题如算法分析之二叉树中描述，二叉树包括完全二叉树，满二叉树，平衡二叉树，二叉搜索树，根据这些不同属性（如深度，节点个数）的树衍生出一系列二叉树问题。
101. 对称二叉树leetcode题目链接：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
解题思路：
对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的，理解这一点就知道了其实我们要比较的是两个树（这两个树是根节点的左右子树），所以在递归遍历的过程中，也是要同时遍历两棵树。
比较的是两个子树的里侧和外侧的元素是否相等。
Java代码实现：
- 递归实现
class Solution {
public boolean isSymmetric(TreeNode root) {
// 递归
if(root == null) return true;
return compare(root.left, root.right);
}
public boolean compare(TreeNode left, TreeNode right) {
if(left != null && right == null) return false;
if(left == null && right != null) return false;
if(left == null && right == null) return true;
if(left.val != right.val) return false;
boolean compare1 = compare(left.left, right.right);
boolean compare2 = compare(left.right, right.left);
return compare1 && compare2;
}
}
- 迭代实现
class Solution {
public boolean isSymmetric(TreeNode root) {
// 迭代，队列
if(root == null) return true;
Queue queue = new linkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while(!queue.isEmpty()) {
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
if(node1 == null && node2 == null) continue;
if(node1 == null || node2 == null || node1.val != node2.val) return false;
queue.offer(node1.left);
queue.offer(node2.right);
queue.offer(node1.right);
queue.offer(node2.left);
}
return true;
}
}
100. 相同的树
leetcode题目链接：100. 相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例一：
输入：p = [1,2,3], q = [1,2,3] 输出：true
解题思路：
相同的树与对称二叉树的思想相似，只是从一棵树换成了两棵树。
Java实现代码：
- 递归
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
return compare(p, q);
}
private boolean compare(TreeNode p, TreeNode q) {
if(p == null && q == null) return true;
if(p == null || q == null || p.val != q.val) return false;
boolean compare1 = compare(p.left, q.left);
boolean compare2 = compare(p.right, q.right);
return compare1 && compare2;
}
}
104. 二叉树的最大深度
leetcode题目链接：104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例一：
给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20
/
15 7
返回它的最大深度 3 。
Java代码实现：
- 递归
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
- 迭代
class Solution {
public int maxDepth(TreeNode root) {
// 迭代，基于层序遍历的队列实现
if(root == null) return 0;
Queue queue = new linkedList<>();
queue.offer(root);
int depth = 0;
while(!queue.isEmpty()) {
int size = queue.size();
depth++;
for(int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
}
return depth;
}
}
111. 二叉树的最小深度
leetcode题目链接：111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例一：
输入：root = [3,9,20,null,null,15,7] 输出：2
需要注意的是：
题目中说的是：最小深度是从根节点到最近叶子节点的最短路径上的节点数量。，注意是叶子节点。
什么是叶子节点，左右孩子都为空的节点才是叶子节点！
所以，如果左子树为空，右子树不为空，说明最小深度是 1 + 右子树的深度。
反之，右子树为空，左子树不为空，最小深度是 1 + 左子树的深度。 最后如果左右子树都不为空，返回左右子树深度最小值 + 1 。
Java代码实现：
- 递归
class Solution {
public int minDepth(TreeNode root) {
// 和最大深度一样，但需要注意的是左右子树为空的情况
if(root == null) return 0;
int left = minDepth(root.left);
int right = minDepth(root.right);
return left == 0 || right == 0 ? 1 + left + right : 1 + Math.min(left, right);
}
}
- 迭代
class Solution {
public int minDepth(TreeNode root) {
// 迭代，基于层序遍历的队列实现
if(root == null) return 0;
Queue queue = new linkedList<>();
queue.offer(root);
int depth = 0;
while(!queue.isEmpty()) {
int size = queue.size();
depth++;
for(int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if(node.left == null && node.right == null){
return depth;
}
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
}
return depth;
}
}
222. 完全二叉树的节点个数
leetcode题目链接：222. 完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2h 个节点。
示例一：
输入：root = [1,2,3,4,5,6] 输出：6
Java代码实现：
- 递归
class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
- 迭代
class Solution {
public int countNodes(TreeNode root) {
// 迭代，基于层序遍历的队列实现
if (root == null) return 0;
Queue queue = new linkedList<>();
queue.offer(root);
int count = 0;
while (!queue.isEmpty()) {
int size = queue.size();
while (size -- > 0) {
TreeNode node = queue.poll();
count++;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return count;
}
}
110. 平衡二叉树
leetcode题目链接：110. 平衡二叉树
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
示例一：
输入：root = [3,9,20,null,null,15,7] 输出：true
解题思路：
这里强调一波概念：
- 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
- 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
但leetcode中强调的深度和高度很明显是按照节点来计算的，如图：
Java代码实现：
- 递归
class Solution {
public boolean isBalanced(TreeNode root) {
// 递归
return getHeight(root) != -1;
}
private int getHeight(TreeNode root) {
if(root == null) return 0;
int left = getHeight(root.left);
int right = getHeight(root.right);
if(left == -1 || right == -1) return -1; // -1表示不平衡，非负表示高度
// 左右高度之差大于1，则不是平衡树
if(Math.abs(left - right) > 1) return -1;
return Math.max(left, right) + 1;
}
}
257. 二叉树的所有路径
leetcode题目链接：257. 二叉树的所有路径
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例一：
输入：root = [1,2,3,null,5] 输出：["1->2->5","1->3"]
Java实现代码：
- 递归
class Solution {
public List binaryTreePaths(TreeNode root) {
List res = new ArrayList<>();
if(root == null) return res;
solve(root, "", res);
return res;
}
private void solve(TreeNode root, String s, List res) {
if(root == null) return;
s += root.val;
if(root.left == null && root.right == null) { // 当前是叶子节点，加入到list
res.add(s);
} else { // 不是叶子节点，继续递归
solve(root.left, s + "->", res);
solve(root.right, s + "->", res);
}
}
}
404. 左叶子之和
leetcode题目链接：404. 左叶子之和
计算给定二叉树的所有左叶子之和。
示例：
3
/
9 20
/
15 7
在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
解题思路：
需要注意的是左叶子节点的判断：如果左节点不为空，且左节点没有左右孩子，那么这个节点就是左叶子。
那么判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。
如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子，判断代码如下：
if(root.left != null && root.left.left == null && root.left.right == null) {
value = root.left.val;
}
Java实现代码：
- 递归
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
if(root == null) return 0;
int left = sumOfLeftLeaves(root.left);
int right = sumOfLeftLeaves(root.right);
int value = 0;
if(root.left != null && root.left.left == null && root.left.right == null) {
value = root.left.val;
}
int sum = value + left + right;
return sum;
}
}
- 迭代
class Solution {
public int sumOfLeftLeaves(TreeNode root) {
// 迭代，层序遍历
if(root == null) return 0;
Queue queue = new linkedList<>();
int sum = 0;
queue.offer(root);
while(!queue.isEmpty()) {
int size = queue.size();
while(size-- > 0) {
TreeNode node = queue.poll();
if(node.left != null) {
queue.offer(node.left);
if(node.left.left == null && node.left.right == null) {
sum += node.left.val;
}
}
if(node.right != null) queue.offer(node.right);
}
}
return sum;
}
}
513. 找树左下角的值
leetcode题目链接：513. 找树左下角的值
给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。
示例一：
输入: root = [2,1,3] 输出: 1
示例二：
输入: [1,2,3,4,null,5,6,null,null,7] 输出: 7
解题思路：
分析一下题目：在树的最后一行找到最左边的值。
首先要是最后一行，然后是最左边的值。
如果使用递归法，如何判断是最后一行呢，其实就是深度最大的叶子节点一定是最后一行。
所以要找深度最大的叶子节点。
那么如果找最左边的呢？可以使用前序遍历，这样才先优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。
迭代法的话，本题使用层序遍历再合适不过了，比递归要好理解的多！
只需要记录最后一行第一个节点的数值就可以了。
Java代码实现：
- 递归
class Solution {
int max = -1;
int res;
public int findBottomLeftValue(TreeNode root) {
dfs(root, 0);
return res;
}
private void dfs(TreeNode root, int depth) {
if(root == null) return;
if(root.left == null && root.right == null) {
if(max < depth) {
max = depth;
res = root.val;
}
}
dfs(root.left, depth + 1);
dfs(root.right, depth + 1);
}
}
- 迭代1
class Solution {
public int findBottomLeftValue(TreeNode root) {
// 迭代，层序遍历
Queue queue = new linkedList<>();
queue.offer(root);
// 记录最后一行的第一个元素
int res = 0;
while(!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if(i == 0) res = node.val;
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
}
return res;
}
}
- 迭代2
class Solution {
public int findBottomLeftValue(TreeNode root) {
// 迭代，层序遍历
Queue queue = new linkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
root = queue.poll();
if(root.right != null) queue.offer(root.right); // 先加右子树节点
if(root.left != null) queue.offer(root.left); // 最后出队的就是左节点
}
return root.val;
}
}
112. 路径总和
leetcode题目链接：112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例一：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。
解题思路：
要遍历从根节点到叶子节点的的路径看看总和是不是目标和。
Java代码实现：
- 递归，回溯，DFS
class Solution {
boolean res = false;
public boolean hasPathSum(TreeNode root, int targetSum) {
dfs(root, targetSum);
return res;
}
public void dfs(TreeNode root, int targetSum){
if(root == null){
return;
}
targetSum -= root.val;
if(root.left == null && root.right == null && targetSum == 0){
res = true;
}
dfs(root.left, targetSum);
dfs(root.right, targetSum);
}
}
- 递归
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) return false;
// 叶子节点
if(root.left == null && root.right == null) return targetSum == root.val;
return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
}
}
2. 二叉树的修改和改造问题
226. 翻转二叉树
leetcode题目链接：226. 翻转二叉树
翻转一棵二叉树。
示例：
输入：
4 / 2 7 / / 1 3 6 9
输出：
4 / 7 2 / / 9 6 3 1
解题思路：
想要翻转它，其实就把每一个节点的左右孩子交换一下就可以了。
Java代码实现：
- 前序遍历
class Solution {
public TreeNode invertTree(TreeNode root) {
// 前序遍历
if(root == null) return null;
TreeNode rightNode = root.right;
// 交换左右子树位置
root.right = invertTree(root.left);
root.left = invertTree(rightNode);
return root;
}
}
- 中序遍历
class Solution {
public TreeNode invertTree(TreeNode root) {
// 中序遍历
if(root == null) return null;
invertTree(root.left); // 递归找到左节点
TreeNode rightNode = root.right;
root.right = root.left;
root.left = rightNode;
// 递归找到右节点，继续交换，此时左右节点已经交换，右节点为root.left
invertTree(root.left);
return root;
}
}
- 后序遍历
class Solution {
public TreeNode invertTree(TreeNode root) {
// 后序遍历
if(root == null) return null;
TreeNode leftNode = invertTree(root.left);
TreeNode rightNode = invertTree(root.right);
root.right = leftNode;
root.left = rightNode;
return root;
}
}
- 层序遍历
class Solution {
public TreeNode invertTree(TreeNode root) {
// 层序遍历,使用队列，直接交换左右节点即可
if(root == null) return null;
Queue queue = new linkedList<>();
queue.offer(root);
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode rightNode = node.right;
node.right = node.left;
node.left = rightNode;
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
return root;
}
}
106. 从中序与后序遍历序列构造二叉树
leetcode题目链接：106. 从中序与后序遍历序列构造二叉树
根据一棵树的中序遍历与后序遍历构造二叉树。
注意:
你可以假设树中没有重复的元素。
例如，给出
中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3]
返回如下的二叉树：
3
/
9 20
/
15 7
解题思路：
以 后序数组的最后一个元素为切割点，先切中序数组，根据中序数组，反过来在切后序数组。一层一层切下去，每次后序数组最后一个元素就是节点元素。
一层一层切割，就应该想到了递归。
来看一下一共分几步：
- 第一步：如果数组大小为零的话，说明是空节点了。
- 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
- 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
- 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
- 第五步：切割后序数组，切成后序左数组和后序右数组
- 第六步：递归处理左区间和右区间
Java代码实现：
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return build(inorder, 0, inorder.length, postorder, 0, postorder.length);
}
public TreeNode build(int[] inorder, int inLeft, int inRight, int[] postorder, int postLeft, int postRight) {
// 树里没有元素
if(inRight - inLeft < 1) return null;
// 只有一个元素
if(inRight - inLeft == 1) return new TreeNode(inorder[inLeft]);
// 后序数组最后一个元素作为根节点
int rootVal = postorder[postRight - 1];
TreeNode root = new TreeNode(rootVal);
// 根据根节点的值找到在中序数组中的位置
int rootIndex = 0;
for(int i = inLeft; i < inRight; i++) {
if(inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
// 根据rootIndex划分左右子树
root.left = build(inorder, inLeft, rootIndex, postorder, postLeft, postLeft + (rootIndex - inLeft));
root.right = build(inorder, rootIndex + 1, inRight, postorder, postLeft + (rootIndex - inLeft), postRight - 1);
return root;
}
}
105. 从前序与中序遍历序列构造二叉树
leetcode题目链接：105. 从前序与中序遍历序列构造二叉树
给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。
示例一：
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7]
解题思路：
与上一题106. 从中序与后序遍历序列构造二叉树类似：
以 前序数组的第一个元素为切割点，先切中序数组，根据中序数组，反过来在切前序数组。一层一层切下去，每次前序数组第一个元素就是根节点元素。
Java实现代码：
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
}
public TreeNode build(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {
// 树里没有元素
if(inLeft > inRight || preRight < preLeft) return null;
// 前序数组第一个元素作为根节点
int rootVal = preorder[preLeft];
TreeNode root = new TreeNode(rootVal);
// 根据根节点的值找到在中序数组中的位置
int rootIndex = 0;
for(int i = inLeft; i <= inRight; i++) {
if(inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
// 根据rootIndex划分左右子树
root.left = build(preorder, preLeft + 1, preLeft + (rootIndex - inLeft), inorder, inLeft, rootIndex - 1);
root.right = build(preorder, preLeft + (rootIndex - inLeft) + 1, preRight, inorder, rootIndex + 1, inRight);
return root;
}
}
654. 最大二叉树
leetcode题目链接：654. 最大二叉树
给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下：
二叉树的根是数组 nums 中的最大元素。 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。
返回有给定数组 nums 构建的 最大二叉树 。
示例一：
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
- 空数组，无子节点。
- [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
- 空数组，无子节点。
- 只有一个元素，所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
- 只有一个元素，所以子节点是一个值为 0 的节点。
- 空数组，无子节点。
解题思路：
与上一题类似，划分区间，递归，先找到最大值所在位置，根据最大值所在位置的下标划分左右子树，再递归左右子树。
Java代码实现：
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
return construct(nums, 0, nums.length);
}
public TreeNode construct(int[] nums, int leftIndex, int rightIndex) {
if (rightIndex - leftIndex < 1) { // 没有元素了
return null;
}
if (rightIndex - leftIndex == 1) { // 只有一个元素
return new TreeNode(nums[leftIndex]);
}
int maxIndex = -1; // 最大值所在位置
int maxVal = -1; // 最大值
// 在nums找到最大值，及对应的下标
for (int i = leftIndex; i < rightIndex; i++) {
if (nums[i] > maxVal){
maxVal = nums[i];
maxIndex = i;
}
}
TreeNode root = new TreeNode(maxVal);
// 根据maxIndex划分左右子树
root.left = construct(nums, leftIndex, maxIndex);
root.right = construct(nums, maxIndex + 1, rightIndex);
return root;
}
}
617. 合并二叉树
leetcode题目链接：617. 合并二叉树
给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。
示例一：
输入:
Tree 1 Tree 2
1 2
/ /
3 2 1 3
/
5 4 7
输出:
合并后的树:
3
/
4 5
/
5 4 7
解题思路：
其实和遍历一个树逻辑是一样的，只不过传入两个树的节点，同时操作。
Java代码实现：
- 递归
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
if(root1 == null) return root2;
if(root2 == null) return root1;
TreeNode newNode = new TreeNode(root1.val + root2.val);
newNode.left = mergeTrees(root1.left, root2.left);
newNode.right = mergeTrees(root1.right, root2.right);
return newNode;
}
}
- 迭代
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
// 迭代
if (root1 == null) return root2;
if (root2 == null) return root1;
Queue queue = new linkedList<>();
queue.offer(root1);
queue.offer(root2);
while (!queue.isEmpty()) {
TreeNode node1 = queue.poll();
TreeNode node2 = queue.poll();
// 此时两个节点一定不为空，val相加
node1.val = node1.val + node2.val;
// 如果两棵树左节点都不为空，加入队列
if (node1.left != null && node2.left != null) {
queue.offer(node1.left);
queue.offer(node2.left);
}
// 如果两棵树右节点都不为空，加入队列
if (node1.right != null && node2.right != null) {
queue.offer(node1.right);
queue.offer(node2.right);
}
// 若node1的左节点为空，直接赋值
if (node1.left == null && node2.left != null) {
node1.left = node2.left;
}
// 若node2的左节点为空，直接赋值
if (node1.right == null && node2.right != null) {
node1.right = node2.right;
}
}
return root1;
}
}
3. 二叉树的公共祖先问题
236. 二叉树的最近公共祖先
leetcode题目链接：236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
示例一：
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
解题思路：
如何判断一个节点是节点q和节点p的公共公共祖先呢。
如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。
使用后序遍历，回溯的过程，就是从低向上遍历节点，一旦发现如何这个条件的节点，就是最近公共节点了。
Java代码实现：
class Solution {
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; // 在左右子树中找到
if(left != null && right == null) return left;
if(left == null && right != null) return right;
return null;
}
}
三、leetcode例题讲解二叉搜索树问题
1. 二叉搜索树的属性问题
700. 二叉搜索树中的搜索
leetcode题目链接：
98. 验证二叉搜索树leetcode题目链接：
530. 二叉搜索树的最小绝对差leetcode题目链接：
501. 二叉搜索树中的众数leetcode题目链接：
538. 把二叉搜索树转换为累加树leetcode题目链接：
2. 二叉搜索树的修改和改造问题 701. 二叉搜索树中的插入操作leetcode题目链接：
450. 删除二叉搜索树中的节点leetcode题目链接：
669. 修剪二叉搜索树leetcode题目链接：
108. 将有序数组转换为二叉搜索树leetcode题目链接：
3. 二叉搜索树的公共祖先问题 235. 二叉搜索树的最近公共祖先leetcode题目链接：
参考：
算法分析之二叉树
算法分析之二叉树遍历
代码随想录：二叉树
