leetcode高频题笔记之二叉树的递归
树是天生的适合递归的数据结构，很多树的问题用递归都可以非常漂亮的解决，而迭代往往比较复杂。熟练使用递归解决下面的二十多个二叉树问题，就能更进一步掌握递归。
普通二叉树
104.二叉树的最大深度
子问题：左右子树中较高的高度作为当前树的高度
public class Solution {
public int maxDepth(TreeNode root) {
return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
} 111.二叉树的最小深度
与二叉树的最大深度有所不同，如果子树为空，最小深度不为1，因为深度定义是到叶子节点的，所以需要处理子树为空的情况
public class Solution {
public int minDepth(TreeNode root) {
//空树返回0
if (root == null) return 0;
//一边树为空返回非空树高度+1
else if (root.left == null && root.right != null) return minDepth(root.right) + 1;
else if (root.left != null && root.right == null) return minDepth(root.left) + 1;
//子树均为空或均不为空返回子树最小高度+1
else return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
} 110.平衡二叉树
自顶向下
子问题：当前树的左右子树高度差小于2，且左右子树都是平衡二叉树
public class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
//如果左右节点高度差小于1，且左右节点都是满足平衡的
return Math.abs(maxDepth(root.left) - maxDepth(root.right)) < 2
&& isBalanced(root.left)
&& isBalanced(root.right);
}
private int maxDepth(TreeNode node) {
return node == null ? 0 : Math.max(maxDepth(node.left), maxDepth(node.right)) + 1;
}
} 自底向上
子问题：获取当前树的左右子树的高度，如果左右子树高度差大于1，设置全局的返回值为false，然后返回树的高度
因为压栈到叶子节点才开始返回，所以是自底向上的，省去了多次获取树的高度
public class Solution {
private boolean res = true;
public boolean isBalanced(TreeNode root) {
maxDepth(root);
return res;
}
private int maxDepth(TreeNode root) {
if (root == null) return 0;
//获取左右子树高度
int left = maxDepth(root.left);
int right = maxDepth(root.right);
//如果发现不是平衡的了就设置为false；
if (Math.abs(left - right) > 1) res = false;
//返回树的高度
return Math.max(left, right) + 1;
}
} 543.二叉树的直径（两节点最大路径）
题意解释：
在二叉树中两个节点可以构成的最长路径
可以不通过根节点的情况
子问题：计算每棵子树的左右子树高度之和，最大值就是整棵树的最大值
和自底向上的求二叉树的高度的代码一致，只是每次获取左右子树高度后计算一个当前最大左右子树和
public class Solution {
private int max = 0;
public int diameterOfBinaryTree(TreeNode root) {
dfs(root);
return max;
}
private int dfs(TreeNode root) {
if (root == null) return 0;
//获取左右子树的高度
int lefth = dfs(root.left);
int righth = dfs(root.right);
//获取左右子树和的最大值
max = Math.max(max, lefth + righth);
//返回树的高度
return Math.max(lefth, righth) + 1;
}
} 687.最长同值路径
思路同上一个题两节点最大路径，自底向上
子问题：求和当前值相等的左右子树的长度的和
public class Solution {
private int path = 0;
public int longestUnivaluePath(TreeNode root) {
dfs(root);
return path;
}
private int dfs(TreeNode root) {
if (root == null) return 0;
//和左子树值相同的串的长度
int left = dfs(root.left);
//和右子树值相同的串的长度
int right = dfs(root.right);
//和当前值相同的左子树长度
int leftPath = root.left != null && root.val == root.left.val ? left + 1 : 0;
//和当前值相同的右子树长度
int rightPath = root.right != null && root.val == root.right.val ? right + 1 : 0;
//比较当前节点的路径更新最长路径
path = Math.max(path, leftPath + rightPath);
//返回当前节点的最长串长度
return Math.max(leftPath, rightPath);
}
} 226.翻转二叉树
子问题：获取左子树和右子树，将左子树赋值给root.tight，右子树赋值给root.left，实现左右子树交换
public 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;
}
} 101.对称二叉树
子问题：判定左子树子左节点和右子树的右节点是否相等，判断左子树的右节点和右子树的左节点是否相等
public class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return helper(root.left, root.right);
}
private boolean helper(TreeNode left, TreeNode right) {
if (left == null && right == null) return true;
if (left == null || right == null) return false;
if (left.val != right.val) return false;
return helper(left.left, right.right) && helper(left.right, right.left);
}
} 617.合并二叉树
子问题：
- 如果两个树的子树都为null,返回null
- 如果一个树的子树为空，返回另一个树的子树
- 如果两个树的子树都不为空，返回两棵树节点值相加的新的节点，新节点的左右子树递归创建
public class Solution {
public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
//如果两个树的子树都为null,返回null
if (t1 == null && t2 == null) return null;
//如果一个树的子树为空，返回另一个树的子树
if (t1 == null) return t2;
if (t2 == null) return t1;
//如果两个树的子树都不为空，返回两棵树节点值相加的新的节点，新节点的左右子树递归创建
TreeNode root = new TreeNode(t1.val + t2.val);
root.left = mergeTrees(t1.left, t2.left);
root.right = mergeTrees(t1.right, t2.right);
return root;
}
} 112.路径总和
子问题：
判断当前节点是不是叶子节点且sum-叶子节点的值为0，满足条件则存在路径
如果不符合就继续看左右节点符不符合，sum的值变为减去当前节点值的新的值
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
//终止条件
if (root == null) return false;
//符合的叶子节点
if (root.left == null && root.right == null && sum - root.val == 0) return true;
//不符合的情况
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
} 437.路径总和III
子问题：求以当前节点为起始的满足的次数和以左右节点为起始满足的次数的和
public class Solution {
public int pathSum(TreeNode root, int sum) {
//终止条件
if (root == null) return 0;
//返回以当前节点为root节点满足的次数+左节点为root满足的次数+右节点为root满足的次数
return pathSumStartWithRoot(root, sum)
+ pathSum(root.left, sum)
+ pathSum(root.right, sum);
}
//计算以root为起始点满足的情况数
private int pathSumStartWithRoot(TreeNode root, int sum) {
if (root == null) return 0;
int ret = 0;
if (root.val == sum) ret++;
ret += pathSumStartWithRoot(root.left, sum - root.val)
+ pathSumStartWithRoot(root.right, sum - root.val);
return ret;
}
} 对于可以从树的任意点为起始点的问题，调用两个递归函数。代码模板：437和572两个题都是类似的
public int mainMethods(TreeNode root){
//退出条件
if (root == null)return 0;
//调用helper函数完成从本节点开始的任务
helper(root);
mainMethods(root.left);
mainMethods(root.right);
return //具体需要的操作
}
//业务操作
private void helper(TreeNode root) {
} 572.另一个树的子树
子问题：层层下探，将每个节点作为t的根节点进行递归比对，如果出现s和t同时为null，说明匹配成功
public class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
if (s == null) return false;
//以s的每个节点作为子树的根节点与t进行递归比对，只要有一个true就算成功了
return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
}
private boolean isSubtreeWithRoot(TreeNode s, TreeNode t) {
//同时为空，说明比对完成了，刚好是子树
if (t == null && s == null) return true;
//只有一个为空，说明数不完全相同，有一边少了
if (t == null || s == null) return false;
//值不相同，匹配失败
if (t.val != s.val) return false;
//匹配成功当前节点，继续递归下探左右节点
return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
}
} 404.左叶子之和
子问题：递归访问左子树和右子树，如果左子树为叶子节点就返回左子树的值
public class Solution {
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;
}
} public class Solution {
public int sumOfLeftLeaves(TreeNode root) {
return root == null ? 0 : ((root.left == null ? false : (root.left.left == null && root.left.right == null)) ? root.left.val : sumOfLeftLeaves(root.left)) + sumOfLeftLeaves(root.right);
}
} 337.打家劫舍III
子问题：选择当前层+下两层的值还是选择下一层的值
public class Solution {
public int rob(TreeNode root) {
if (root == null) return 0;
int val1 = root.val;
if (root.left != null) val1 += rob(root.left.left) + rob(root.left.right);
if (root.right != null) val1 += rob(root.right.left) + rob(root.right.right);
int val2 = rob(root.left) + rob(root.right);
return Math.max(val1, val2);
}
} 671.二叉树中第二小的节点
子问题：查看当前节点的子节点值是否大于节点值，如果不是，就递归查找大于的值返回
public class Solution {
public int findSecondMinimumValue(TreeNode root) {
//如果当前节点是空节点，或者当前节点的下一层是空节点，则说明没找到，返回-1
if (root == null || root.left == null || root.right == null) return -1;
//获取左右子节点的值
int leftv = root.left.val;
int rightv = root.right.val;
//如果子节点的值和当前节点相等，就下探找子树中符合的节点
if (root.val == leftv) leftv = findSecondMinimumValue(root.left);
if (root.val == rightv) rightv = findSecondMinimumValue(root.right);
//如果两个子树都找到了大于根节点的值，返回最小值
if (leftv != -1 && rightv != -1) return Math.min(leftv, rightv);
//如果只有左子树存在就返回左子树的
if (leftv != -1) return leftv;
//如果只有右子树存在就返回右子树的
return rightv;
}
} BST
669.修剪二叉搜索树
子问题：
- 如果根节点值大于R，说明新树都在左子树，修剪左子树
- 如果根节点值小于L，说明新树都在右子树，修剪右子树
- 如果根节点值位于[L,R]，修剪左右子树后返回根节点
public class Solution {
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) return root;
//新树在根节点左边
if (root.val > R) return trimBST(root.left, L, R);
//新树在根节点右边
if (root.val < L) return trimBST(root.right, L, R);
//新树包含了根节点，左右修剪返回根节点
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
} 230.二叉搜索树中第K小的元素
中序遍历：利用BST中序遍历结果是升序的特点
public class Solution {
private int count = 0;
private int val;
public int kthSmallest(TreeNode root, int k) {
search(root, k);
return val;
}
private void search(TreeNode root, int k) {
if (root == null) return;
search(root.left, k);
count++;
if (count == k) {
val = root.val;
return;
}
search(root.right, k);
}
} 递归：
子问题：
统计左子树节点个数，如果节点数+1等于k则找到值，如果不等于就向左右子树递归
public class Solution {
public int kthSmallest(TreeNode root, int k) {
if (root.left == null) return kthSmallest(root.right, k);
//统计左子树个节点数
int leftcount = count(root.left);
//如果左子树节点+1等于k，则说明根节点就是需要找的
if (leftcount + 1 == k) return root.val;
//如果左子树节点+1大于k，则说明需要找的节点再根节点左边，调用左节点
if (leftcount + 1 > k) return kthSmallest(root.left, k);
//如果左子树节点+1小于k，则说明需要找的节点再根节点右边，调用右节点，更新k的值为减去了左子树节点加根节点的数目
return kthSmallest(root.right, k - leftcount - 1);
}
//统计这棵树的非空节点个数
private int count(TreeNode root) {
return root == null ? 0 : 1 + count(root.left) + count(root.right);
}
} 538.把二叉搜索树转换为累加树
利用BST中序遍历是升序的基础，如果交换遍历顺序就是降序遍历，只需要一个全局变量暂存之前的值就可以做到累加
public class Solution {
private int sum = 0;
public TreeNode convertBST(TreeNode root) {
search(root);
return root;
}
private void search(TreeNode root) {
if (root == null) return;
search(root.right);
sum += root.val;
root.val = sum;
search(root.left);
}
} 235.二叉搜索树的最近公共祖先
子问题：
- 如果两个节点值都小于根节点，说明公共祖先在左子树
- 如果两个节点值都大于根节点，说明公共祖先在又子树
- 其他情况，公共祖先就是根节点
public class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { //两个节点都小于根节点，访问左节点 if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q); //两个节点都大于根节点，访问右节点 if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q); //两个节点有一个等于根节点或者一个大于根节点一个小于根节点，根节点都符合公共祖先定义 else return root; } }98.验证二叉搜索树
public class Solution {
long last = Long.MIN_VALUE;
public boolean isValidBST(TreeNode root) {
if (root == null) return true;
//遍历左节点，如果无序返回falsae
if (!isValidBST(root.left)) return false;
//当前层不是有序的
if (root.val <= last) return false;
last = root.val;
//遍历右节点，如果无序返回false
if (!isValidBST(root.right)) return false;
return true;
}
} 108.将有序数组转换为二叉搜索树
二分查找时的查找状态树其实就是一个二分搜索树，所以模拟二分查找就可以构建一棵BST
public class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return toBST(nums, 0, nums.length - 1);
}
private TreeNode toBST(int[] nums, int sIndex, int eIndex) {
if (sIndex > eIndex) return null;
int mIndex = (sIndex + eIndex) << 1;//防止恶心的边界值越界
TreeNode root = new TreeNode(nums[mIndex]);
root.left = toBST(nums, sIndex, mIndex - 1);
root.right = toBST(nums, mIndex + 1, eIndex);
return root;
}
} 109.有序链表转换二叉搜索树
和上一题将有序数组转换为二叉搜索树思路一致，通过二分排序的状态树构建BFS
没有了下标计算获取中点，可以通过快慢指针来寻找链表的中点
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
if (head.next == null) return new TreeNode(head.val);
ListNode preMid = preMid(head);//获取中点的前一个节点
ListNode mid = preMid.next;//获取中点
preMid.next = null;//断开两个链表
TreeNode root = new TreeNode(mid.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(mid.next);
return root;
}
//快慢指针寻找链表中点前一个节点，为了完成断开链表
private ListNode preMid(ListNode head) {
ListNode fast = head.next;
ListNode slow = head;
ListNode pre = head;
while (fast != null && fast.next != null) {
pre = slow;
slow = slow.next;
fast = fast.next.next;
}
return pre;
}
} 653.两数之和IV-输入BST
利用BST中序遍历有序的特性，先采用中序遍历，然后采用双指针查询
public class Solution {
List<Integer> nums;
public boolean findTarget(TreeNode root, int k) {
nums = new ArrayList<>();
//中序遍历
search(root);
//双指针查找
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int compare = nums.get(left) + nums.get(right);
if (compare == k) return true;
else if (compare > k) right--;
else left++;
}
return false;
}
//中序遍历
private void search(TreeNode root) {
if (root == null) return;
search(root.left);
nums.add(root.val);
search(root.right);
}
} 530.二叉搜索树的最小绝对差
利用BST中序遍历是升序的特点，逐个比较差值，记录最小的差值返回
public class Solution {
int min = Integer.MAX_VALUE;//最小差值
int pre = -1;//上一个节点的值
public int getMinimumDifference(TreeNode root) {
search(root);
return min;
}
//中序遍历
private void search(TreeNode root) {
if (root == null) return;
search(root.left);
if (pre != -1) {//如果访问的不是第一个节点
min = Math.min(min, root.val - pre);
}
pre = root.val;
search(root.right);
}
} 501.二叉搜索树中的众数
充分利用BST中序遍历是升序的，具体逻辑见代码
public class Solution {
List<Integer> nums;//众数集合
int curcount = 0;//当前计数
int maxcount = 0;//最大个数
Integer pre = null;//前一个节点的值，为了判断第一个节点，用包装类初始化为null
public int[] findMode(TreeNode root) {
nums = new ArrayList<>();
search(root);
//复制list值到数组
int res[] = new int[nums.size()];
for (int i = 0; i < nums.size(); i++) {
res[i] = nums.get(i);
}
return res;
}
private void search(TreeNode root) {
if (root == null) return;
search(root.left);
//不是第一个节点且与前一个值相同，计数加1
if (pre != null && pre == root.val) curcount++;
//第一个节点或者与前一个值不同，计数更新为1
else curcount = 1;
//如果当前计数和最大计数相同，将当前值加入众数集合
if (curcount == maxcount) nums.add(root.val);
//如果当前计数大于最大计数，清空众数集合，加入当前值，更新最佳计数
else if (curcount > maxcount) {
nums.clear();
nums.add(root.val);
maxcount = curcount;
}
//暂存值
pre = root.val;
search(root.right);
}
} leetcode分类题集 文章被收录于专栏
按知识点分类整理leetcode的题目和解法
查看6道真题和解析
