二叉树高频题目-下-不含树型dp

本文主要是介绍二叉树高频题目-下-不含树型dp，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

二叉树高频题目-下-不含树型dp

题目1 : 普通二叉树上寻找两个节点的最近公共祖先(lca问题)

• 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/

• 思路

  • 分别在该树的左右子树上搜索, 当该树为 空 或 p 或 q, 直接返回
    • 若返回的是p 或 q , 那么该结点会一直向上传递直到遇到最近公共祖先
  • 若左右子树都搜到, 返回root
    • 此时pq分别在root两侧, root就是其最近的公共祖先
  • 整颗树都没有搜到, 返回空
  • 若l r搜到其中一个, 返回不为空的那个
    • 此时pq一定在同一侧, 另一个就在不为空的那个子树上

• 代码

  • 	public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root == null || root == p || root == q) {// 遇到空，或者p，或者q，直接返回return root;}// 左树搜索p和q: 遇到空，或者p，或者q，直接返回TreeNode l = lowestCommonAncestor(root.left, p, q);// 右树搜索p和q: 遇到空，或者p，或者q，直接返回TreeNode r = lowestCommonAncestor(root.right, p, q);if (l != null && r != null) {// 左树也搜到，右树也搜到，返回rootreturn root;}if (l == null && r == null) {// 整棵树都没搜到返回空return null;}// l和r一个为空，一个不为空// 返回不空的那个return l != null ? l : r;}
    

题目2 : 搜索二叉树上寻找两个节点的最近公共祖先

搜索二叉树又称: 二叉搜索树，二叉排序树

• 测试链接 : https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
• 思路
  • 若root在p~q的左侧, 那么pq都比root的值大, 就往root的右子树上搜索
  • 若root在p~q的右侧, 那么pq都比root的值小, 就往root的左子树上搜索
  • 若root在p~q之间, 则root就是两个节点的最近公共祖先
  • 否则若先遇到了p, 说明最近公共祖先是p, q在p的子树上
  • 否则若先遇到了q, 说明最近公共祖先是q, p在q的子树上

注: 3 4 5 点不可能同时成立, 若3成立, 4 5 就不可能出现, 若 4 5 出现, 说明pq的最近公共祖先大小一定不在pq之间, 否则在3条件满足时就会返回

• 代码

  • 	public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// root从上到下// 如果先遇到了p，说明p是答案// 如果先遇到了q，说明q是答案// 如果root在p~q的值之间，不用管p和q谁大谁小，只要root在中间，那么此时的root就是答案// 如果root在p~q的值的左侧，那么root往右移动// 如果root在p~q的值的右侧，那么root往左移动while (root.val != p.val && root.val != q.val) {// 没有遇到p 也没有遇到qif (Math.min(p.val, q.val) < root.val && root.val < Math.max(p.val, q.val)) {break;// root在p 和 q之间, 返回root}// 没有在中间, 也不是p或q, 向需要的方向移动root = root.val < Math.min(p.val, q.val) ? root.right : root.left;}return root;}
    

题目3 : 收集累加和等于aim的所有路径(递归恢复现场)

• 测试链接 : https://leetcode.cn/problems/path-sum-ii/

• 思路

  • 设置最终返回的答案和全局路径, 从根节点开始递归
  • 判断当前结点是否为叶节点
    • 是叶节点: 判断是否符合要求
      • 符合: 之前路径累加和 + 当前结点的值 == 目标值
        • 将该节点值加入全局路径中
        • 将该路径复制 (全局路径是同一地址, 使用原集合会使后面的路径覆盖之前的路径) 一份放入ans中
        • 将该结点从路径中删除(恢复现场)
      • 不符合: 不做任何操作(path不变, 路径不变)
    • 不是叶节点
      • 将该节点加入全局路径中去
      • 若左子树不为空, 跑左侧递归
      • 若右子树不为空, 跑右侧递归
      • 将该结点从路径中删除(恢复现场)

• 代码

  • 	public static List<List<Integer>> pathSum(TreeNode root, int aim) {List<List<Integer>> ans = new ArrayList<>();// 要返回的大结果if (root != null) {List<Integer> path = new ArrayList<>();// 全局路径: 只维持上方路径的所有节点f(root, aim, 0, path, ans);// 处理}return ans;// 如果整棵树是空的, 没有路径}public static void f(TreeNode cur, int aim, int sum, List<Integer> path, List<List<Integer>> ans) {//			  当前来到的结点     目标和  cur上方路径的累加和  全局path		            结果if (cur.left == null && cur.right == null) {  // 当前结点是叶节点if (cur.val + sum == aim) {// 叶节点达标 当前路径满足要求path.add(cur.val);// 把自己的值 放到 路径中去copy(path, ans);// path拷贝一份, 放入anspath.remove(path.size() - 1);// 返回前 把自己移除掉(当前结点是叶节点:path中的最后一个)}// 叶节点不达标, 什么也不操作, 直接返回} else {// 当前结点不是叶节点path.add(cur.val);// 把自己加到路径中if (cur.left != null) {// 跑左侧的递归f(cur.left, aim, sum + cur.val, path, ans);}if (cur.right != null) {// 跑右侧的递归f(cur.right, aim, sum + cur.val, path, ans);}path.remove(path.size() - 1);// 把自己从路径中删掉 即 恢复现场}}public static void copy(List<Integer> path, List<List<Integer>> ans) {List<Integer> copy = new ArrayList<>();for (Integer num : path) {copy.add(num);}ans.add(copy);}
    

题目4 : 验证平衡二叉树(树型dp沾边)

• 测试链接 : https://leetcode.cn/problems/balanced-binary-tree/

• 思路

  • 递归求二叉树的高度, 根据Math.abs(lh - rh) > 1来判断二叉树是否平衡, 不平衡则将全局变量balance改为false, 返回(此时树高可返回任何值), 平衡则返回树高

• 代码

  • 	public static boolean balance;public static boolean isBalanced(TreeNode root) {// balance是全局变量，所有调用过程共享// 所以每次判断开始时，设置为默认值truebalance = true;// 根本目的是验证平衡二叉树, 查找树高只是辅助判断height(root);return balance;}// 一旦发现不平衡，返回什么高度已经不重要了public static int height(TreeNode cur) {if (!balance || cur == null) {// 此处可以不加 !balance , 在最后也会返回(当!balance成立时, 返回什么就不重要了)return 0;}int lh = height(cur.left);int rh = height(cur.right);if (Math.abs(lh - rh) > 1) {balance = false;}return Math.max(lh, rh) + 1;}
    

题目5 : 验证搜索二叉树(树型dp沾边)

• 测试链接 : https://leetcode.cn/problems/validate-binary-search-tree/

• 思路1

  • 中序遍历二叉树, 查看个节点是否满足 左 < 中 < 右

• 代码1

  • 	public static int MAXN = 10001;public static TreeNode[] stack = new TreeNode[MAXN];public static int r;// 提交时改名为isValidBSTpublic static boolean isValidBST1(TreeNode head) {if (head == null) {// 如果树为空, 该树为BSTreturn true;}// 非递归的形式实现二叉树的遍历TreeNode pre = null;// 前一个节点r = 0;while (r > 0 || head != null) {if (head != null) {// 左stack[r++] = head;head = head.left;} else {head = stack[--r];// 根if (pre != null && pre.val >= head.val) {// 有之前的节点 且 之前的节点和现在的节点不符合要求return false;}pre = head;head = head.right;// 右}}// whilereturn true;}
    

• 思路2

  • 递归判断二叉树是否满足 左 < 中 < 右
    • 1. 空树一定为搜索二叉树
      2. 左边是不是搜索二叉树, 用两个变量接住左树上的最大和最小
      3. 右边是不是搜索二叉树, 用两个变量接住左树上的最大和最小
      4. 保存整棵树的 最大最小值 给 全局变量, 使 上游的树 能够接收到
      5. 判断 左树是BST 右树是BST lmax < cur,val < rmin, 返回该树是不是BST

• 代码2

  • 	public static long min, max;// 全局变量, 用于每个节点确定自己的lmax rmin// 提交时改名为isValidBSTpublic static boolean isValidBST2(TreeNode head) {if (head == null) {// 1. 空树一定为搜索二叉树min = Long.MAX_VALUE;max = Long.MIN_VALUE;// lmax < cur,val < rmin, 使其满足程序要求return true;}boolean lok = isValidBST2(head.left);// 2. 左边是不是搜索二叉树// 用两个变量接住左树上的最大和最小long lmin = min;long lmax = max;boolean rok = isValidBST2(head.right);// 3. 右边是不是搜索二叉树// 用两个变量接住左树上的最大和最小long rmin = min;long rmax = max;// 4. 保存整棵树的 最大最小值 给 全局变量, 使 上游的树 能够接收到min = Math.min(Math.min(lmin, rmin), head.val);// 整棵树的最小值max = Math.max(Math.max(lmax, rmax), head.val);// 整棵树的最大值// 5. 返回该树是不是BST// 左树是BST 右树是BST  lmax < cur,val < rminreturn lok && rok && lmax < head.val && head.val < rmin;}
    

题目6 : 修剪搜索二叉树

• 测试链接 : https://leetcode.cn/problems/trim-a-binary-search-tree/

• 思路

  • 递归, 判断整棵树保留什么, 将保留的重新连好, 返回

    • 当前是空节点: 返回空
    • 当前值小于最小值, 则我和左子树(比我小)都不符合条件, 去右子树找
    • 当前值大于最大值, 则我和右子树(比我大)都不符合条件, 去左子树找
    • cur在范围中, cur一定会被保留, 去找cur符合要求的左孩子, 去找cur符合要求的右孩子

  • 代码

    • 	// [low, high]public static TreeNode trimBST(TreeNode cur, int low, int high) {// 当前是空节点: 返回空if (cur == null) {return null;}// 当前值小于最小值, 则我和左子树都不符合条件, 去右子树找if (cur.val < low) {return trimBST(cur.right, low, high);}// 当前值大于最大值, 则我和右子树都不符合条件, 去左子树找if (cur.val > high) {return trimBST(cur.left, low, high);}// cur在范围中, cur一定会被保留cur.left = trimBST(cur.left, low, high);cur.right = trimBST(cur.right, low, high);return cur;}
      

题目7 : 二叉树打家劫舍问题(树型dp沾边)

• 测试链接 : https://leetcode.cn/problems/house-robber-iii/

• 思路

  • 递归 + 全局变量

    • yes : 偷头节点的情况下，最大的收益
    • no : 在不偷头节点的情况下，最大的收益
    • 若当前节点为null, yes == no == 0
    • 返回 Math.max(yes, no)

  • 局部变量: y, n表示 当前节点偷头节点的情况下，最大的收益 和 在不偷头节点的情况下，最大的收益

    • y + no-l + no-r: 一旦该结点偷头结点, 那么相邻的子节点就不能偷

    • n + Math.max(yes-l, no-l) + Math.max(yes-r, no-r)

    • 将全局变量yes置为当前的y 将全局变量no置为当前的n

    • 返回程序

• 代码

  • 	public static int rob(TreeNode root) {f(root);// 整棵树的yes 和 no被返回return Math.max(yes, no);// 返回整棵树中yes 和 no的最大值}// 全局变量，完成了X子树的遍历，返回之后// yes变成，X子树在偷头节点的情况下，最大的收益public static int yes;// 全局变量，完成了X子树的遍历，返回之后// no变成，X子树在不偷头节点的情况下，最大的收益public static int no;public static void f(TreeNode root) {// 计算x子树 偷与不偷头结点 的最大受益的具体函数if (root == null) {// 如果为空, 都是0的受益yes = 0;no = 0;} else {// root自身的yes 和 noint y = root.val;int n = 0;f(root.left);// 该函数调用后, 全局变量yes为左树偷头结点的最好收益, no为左树不偷头结点的最好受益y += no;// 自己的y只能+底层的non += Math.max(yes, no);// 自己的no+底层更大的那个// 同样方式调用并加上右边f(root.right);y += no;n += Math.max(yes, no);// 自己返回前, 要把自己的yes和no更新到全局变量上yes = y;no = n;}}
    

这篇关于二叉树高频题目-下-不含树型dp的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---