• 树递归技巧

    • 如果需要搜索整颗二叉树而且不用处理返回值，递归函数就不要有返回值

    • 如果需要搜索整颗二叉树而且需要处理返回值，递归函数就需要有返回值

    • 如果要搜索其中一条符合条件的路径，那么就必须要有返回值，遇到了符合的就返回

    【如果需要搜索整颗二叉树而且不用处理返回值，递归函数就不要有返回值】

    【1】给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

    需要遍历整颗二叉树，每个节点的左右子节点进行一次交换就行

    1.  
    2. public TreeNode invertTree(TreeNode root) {
    3.         search(root);
    4.         return root;
    5.  
    6. }
    7. public void search(TreeNode root){
    8.         if(root == null)
    9.             return root;
    10.         invertTree(root.left);
    11.         invertTree(root.right);
    12.         TreeNode temp;
    13.         temp = root.left;
    14.         root.left = root.right;
    15.         root.right = temp;
    16. }

    【2】给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

    1. class Solution {
    2.     public List binaryTreePaths(TreeNode root) {
    3.         List res = new ArrayList<>();
    4.         if (root == null) {
    5.             return res;
    6.         }
    7.         List paths = new ArrayList<>();
    8.         traversal(root, paths, res);
    9.         return res;
    10.     }
    11.  
    12.     private void traversal(TreeNode root, List paths, List res) {
    13.         paths.add(root.val);
    14.         // 叶子结点
    15.         if (root.left == null && root.right == null) {
    16.             // 输出
    17.             StringBuilder sb = new StringBuilder();
    18.             for (int i = 0; i < paths.size() - 1; i++) {
    19.                 sb.append(paths.get(i)).append("->");
    20.             }
    21.             sb.append(paths.get(paths.size() - 1));
    22.             res.add(sb.toString());
    23.             return;
    24.         }
    25.         if (root.left != null) {
    26.             traversal(root.left, paths, res);
    27.             paths.remove(paths.size() - 1);// 回溯
    28.         }
    29.         if (root.right != null) {
    30.             traversal(root.right, paths, res);
    31.             paths.remove(paths.size() - 1);// 回溯
    32.         }
    33.     }
    34. }

    【3】

    【如果需要搜索整颗二叉树而且需要处理返回值，递归函数就需要有返回值】

    1. //##########递归模板##########
    2. // 接住返回值
    3. 左返回值  = search(root.left);
    4. 右返回值  = search(root.right);
    5. 逻辑处理左右返回值+自身节点逻辑处理  返回
    6.  
    7. 主要就是逻辑处理，
    8. 左子树，右子树搜索到的结果直接返回么？
    9. 或者考虑两者关系后直接返回？
    10. 或者考虑父节点和自身关系返回？

    【1】给你一个二叉树的根节点 root ， 检查它是否轴对称。

    1. class Solution {
    2.     public boolean isSymmetric(TreeNode root) {
    3.         return check(root, root);
    4.     }
    5.  
    6.     public boolean check(TreeNode p, TreeNode q) {
    7.         if (p == null && q == null) {
    8.             return true;
    9.         }
    10.         if (p == null || q == null) {
    11.             return false;
    12.         }
    13.         boolean left = check(p.left, q.right);
    14.         boolean right = check(p.right, q.left);
    15.         return p.val == q.val && left  && right ;
    16.     }
    17. }

    【2】二叉树最大深度  比较每个子树的深度，取最大深度

    1. class Solution {
    2.     public int maxDepth(TreeNode root) {
    3.         if(root == null)
    4.             return 0;
    5.         int leftDepth = maxDepth(root.left);
    6.         int rightDepth = maxDepth(root.right);
    7.         return (leftDepth>rightDepth?leftDepth:rightDepth)  + 1;
    8.     }
    9. }

    【3】求最小深度

    1. class Solution {
    2.     public int minDepth(TreeNode root) {
    3.         if(root == null)
    4.             return 0;
    5.         
    6.         int leftDepth = minDepth(root.left);
    7.         int rightDepth = minDepth(root.right);
    8.         if(leftDepth == 0)
    9.             return rightDepth+1;
    10.         if(rightDepth==0)
    11.             return leftDepth+1;
    12.         return Math.min(leftDepth,rightDepth)+1；
    13.     }
    14. }

    【4】给定一个二叉树，判断它是否是高度平衡的二叉树。

    1. class Solution {
    2.     public boolean isBalanced(TreeNode root) {
    3.         return depth(root) != -1;
    4.     }
    5.     public int depth(TreeNode root){
    6.         if(root == null)
    7.             return 0;
    8.         int l_Depth = depth(root.left);
    9.         if(l_Depth == -1)
    10.             return -1;
    11.         int r_Depth = depth(root.right);
    12.         if(r_Depth == -1)
    13.             return -1;
    14.         if(Math.abs(l_Depth-r_Depth)>1)
    15.             return -1;
    16.         return Math.max(l_Depth,r_Depth) +1;
    17.     }
    18. }

    【5】给定二叉树的根节点 root ，返回所有左叶子之和。

    【6】给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

    1. class Solution {
    2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    3.         if (root == null || root == p || root == q) { // 递归结束条件
    4.             return root;
    5.         }
    6.  
    7.         // 后序遍历
    8.         TreeNode left = lowestCommonAncestor(root.left, p, q);
    9.         TreeNode right = lowestCommonAncestor(root.right, p, q);
    10.  
    11.         if(left == null && right == null) { // 若未找到节点 p 或 q
    12.             return null;
    13.         }else if(left == null && right != null) { // 若找到一个节点
    14.             return right;
    15.         }else if(left != null && right == null) { // 若找到一个节点
    16.             return left;
    17.         }else { // 若找到两个节点
    18.             return root;
    19.         }
    20.     }
    21. }

    【搜索其中一条符合条件的路径，那么就必须要有返回值，遇到了符合的就返回】

    说白了也可以理解为上面，逻辑处理都可以包含

    【1】 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。叶子节点 是指没有子节点的节点。

    1. //=====代码模板====
    2. if(search(root.left))
    3.     return;
    4. if(search(root.right))
    5.     return;
    1. class solution {
    2.    public boolean haspathsum(treenode root, int targetsum) {
    3.         if (root == null) {
    4.             return false;
    5.         }
    6.         targetsum -= root.val;
    7.         // 叶子结点
    8.         if (root.left == null && root.right == null) {
    9.             return targetsum == 0;
    10.         }
    11.         if (root.left != null) {
    12.             boolean left = haspathsum(root.left, targetsum);
    13.             if (left) {// 已经找到
    14.                 return true;
    15.             }
    16.         }
    17.         if (root.right != null) {
    18.             boolean right = haspathsum(root.right, targetsum);
    19.             if (right) {// 已经找到
    20.                 return true;
    21.             }
    22.         }
    23.         return false;
    24.     }
    25. }

    【2】在二叉搜索树查

    1. class Solution {
    2.     // 递归，利用二叉搜索树特点，优化
    3.     public TreeNode searchBST(TreeNode root, int val) {
    4.         if (root == null || root.val == val) {
    5.             return root;
    6.         }
    7.         if (val < root.val) {
    8.             return searchBST(root.left, val);
    9.         } else {
    10.             return searchBST(root.right, val);
    11.         }
    12.     }
    13. }

    【3】二叉搜索树寻找两个节点数值之间就是公共节点

    1.  
    2. class Solution {
    3.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    4.         if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q);
    5.         if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q);
    6.         return root;
    7.     }
    8. }

    【植树造林】记一种[left，right）

    【1】中序+后序确定树

    1. class Solution {
    2.     Map map;  // 方便根据数值查找位置
    3.     public TreeNode buildTree(int[] inorder, int[] postorder) {
    4.         map = new HashMap<>();
    5.         for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
    6.             map.put(inorder[i], i);
    7.         }
    8.  
    9.         return findNode(inorder,  0, inorder.length, postorder,0, postorder.length);  // 前闭后开
    10.     }
    11.     
    12.     public TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
    13.         // 参数里的范围都是前闭后开
    14.         if (inBegin >= inEnd || postBegin >= postEnd) {  // 不满足左闭右开，说明没有元素，返回空树
    15.             return null;
    16.         }
    17.         int rootIndex = map.get(postorder[postEnd - 1]);  // 找到后序遍历的最后一个元素在中序遍历中的位置
    18.         TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
    19.         int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定后序数列的个数
    20.         root.left = findNode(inorder, inBegin, rootIndex,
    21.                             postorder, postBegin, postBegin + lenOfLeft);
    22.         root.right = findNode(inorder, rootIndex + 1, inEnd,
    23.                             postorder, postBegin + lenOfLeft, postEnd - 1);
    24.  
    25.         return root;
    26.     }
    27. }

    【2】前序+中序确定树 

    1. class Solution {
    2.     Map map;
    3.     public TreeNode buildTree(int[] preorder, int[] inorder) {
    4.         map = new HashMap<>();
    5.         for (int i = 0; i < inorder.length; i++) { // 用map保存中序序列的数值对应位置
    6.             map.put(inorder[i], i);
    7.         }
    8.  
    9.         return findNode(preorder, 0, preorder.length, inorder,  0, inorder.length);  // 前闭后开
    10.     }
    11.  
    12.     public TreeNode findNode(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
    13.         // 参数里的范围都是前闭后开
    14.         if (preBegin >= preEnd || inBegin >= inEnd) {  // 不满足左闭右开，说明没有元素，返回空树
    15.             return null;
    16.         }
    17.         int rootIndex = map.get(preorder[preBegin]);  // 找到前序遍历的第一个元素在中序遍历中的位置
    18.         TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造结点
    19.         int lenOfLeft = rootIndex - inBegin;  // 保存中序左子树个数，用来确定前序数列的个数
    20.         root.left = findNode(preorder, preBegin + 1, preBegin + lenOfLeft + 1,  
    21.                             inorder, inBegin, rootIndex);
    22.         root.right = findNode(preorder, preBegin + lenOfLeft + 1, preEnd,
    23.                             inorder, rootIndex + 1, inEnd);
    24.  
    25.         return root;
    26.     }
    27. }

    【3】给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

    1. class Solution {
    2.     public TreeNode constructMaximumBinaryTree(int[] nums) {
    3.         return constructMaximumBinaryTree1(nums, 0, nums.length);
    4.     }
    5.  
    6.     public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {
    7.         if (rightIndex - leftIndex < 1) {// 没有元素了
    8.             return null;
    9.         }
    10.         if (rightIndex - leftIndex == 1) {// 只有一个元素
    11.             return new TreeNode(nums[leftIndex]);
    12.         }
    13.         int maxIndex = leftIndex;// 最大值所在位置
    14.         int maxVal = nums[maxIndex];// 最大值
    15.         for (int i = leftIndex + 1; i < rightIndex; i++) {
    16.             if (nums[i] > maxVal){
    17.                 maxVal = nums[i];
    18.                 maxIndex = i;
    19.             }
    20.         }
    21.         TreeNode root = new TreeNode(maxVal);
    22.         // 根据maxIndex划分左右子树
    23.         root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);
    24.         root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);
    25.         return root;
    26.     }
    27. }

    【4】给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

    1. class Solution {
    2.     public TreeNode sortedArrayToBST(int[] nums) {
    3.         return travesal(nums,0,nums.length );
    4.     }
    5.     public TreeNode travesal(int[] nums, int left,int right){
    6.         if(left >= right)
    7.             return null;
    8.         if(right - left == 1)
    9.             return new TreeNode(nums[left]);
    10.         int mid = left + (right - left) / 2;
    11.         TreeNode root = new TreeNode(nums[mid]);
    12.         root.left = travesal(nums,left,mid);
    13.         root.right = travesal(nums,mid+1,right);
    14.         return root;
    15.     }
    16. }

    【修树改树】

    1. //#############模板##############
    2. root.left = search(root.left);
    3. root.right = search(root.right)
    4. 递归时候确保每个节点的修树改树正确

    【1】给你两棵二叉树： root1 和 root2 。返回合并后的二叉树。注意: 合并过程必须从两个树的根节点开始。

    1. class Solution {
    2.     public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    3.         if(root1 == null && root2 == null)
    4.             return null;
    5.         if(root1 == null)
    6.             return root2;
    7.         if(root2 == null)
    8.             return root1;
    9.         root1.val += root2.val;
    10.         root1.left = mergeTrees(root1.left,root2.left);
    11.         root1.right = mergeTrees(root1.right,root2.right);
    12.         return root1;
    13.     }
    14. }

    【2】给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value 

    1. class Solution {
    2.     public TreeNode insertIntoBST(TreeNode root, int val) {
    3.         if (root == null) // 如果当前节点为空，也就意味着val找到了合适的位置，此时创建节点直接返回。
    4.             return new TreeNode(val);
    5.             
    6.         if (root.val < val){
    7.             root.right = insertIntoBST(root.right, val); // 递归创建右子树
    8.         }else if (root.val > val){
    9.             root.left = insertIntoBST(root.left, val); // 递归创建左子树
    10.         }
    11.         return root;
    12.     }
    13. }
    14.  
    15.

    【3】给定二叉搜索树（BST）的根节点 root 和要删除树中的值 value 

    详解

     

    1. class Solution {
    2.     public TreeNode deleteNode(TreeNode root, int key) {
    3.         root = delete(root,key);
    4.         return root;
    5.     }
    6.  
    7.     private TreeNode delete(TreeNode root, int key) {
    8.         if (root == null) return null;
    9.  
    10.         if (root.val > key) {
    11.             root.left = delete(root.left,key);
    12.         } else if (root.val < key) {
    13.             root.right = delete(root.right,key);
    14.         } else {
    15.             if (root.left == null) return root.right;
    16.             if (root.right == null) return root.left;
    17.             TreeNode tmp = root.right;
    18.             while (tmp.left != null) {
    19.                 tmp = tmp.left;
    20.             }
    21.             root.val = tmp.val;
    22.             root.right = delete(root.right,tmp.val);
    23.         }
    24.         return root;
    25.     }
    26. }

    【4】给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。

    1. class Solution {
    2.     public TreeNode trimBST(TreeNode root, int low, int high) {
    3.         if (root == null) {
    4.             return null;
    5.         }
    6.         if (root.val < low) {
    7.             return trimBST(root.right, low, high);
    8.         }
    9.         if (root.val > high) {
    10.             return trimBST(root.left, low, high);
    11.         }
    12.         // root在[low,high]范围内
    13.         root.left = trimBST(root.left, low, high);
    14.         root.right = trimBST(root.right, low, high);
    15.         return root;
    16.     }
    17. }

    【其他类型】

    【回溯】int型不需要，引用类型需要，list添加后，返回上一层依然还在

    【求深度】与求高度不同，参数列表添加标记

    1.  
    2.     private void findLeftValue (TreeNode root,int deep) {
    3.         if (root == null) return;
    4.         if (root.left == null && root.right == null) {
    5.             if (deep > Deep) {
    6.                 value = root.val;
    7.                 Deep = deep;
    8.             }
    9.         }
    10.         if (root.left != null) findLeftValue(root.left,deep + 1);
    11.         if (root.right != null) findLeftValue(root.right,deep + 1);
    12.     }

    【参数列表添加标记】左叶子之和

    1. class Solution {
    2.     public int sumOfLeftLeaves(TreeNode root) {
    3.         return sum(root,false);
    4.     }
    5.     public int sum(TreeNode root, boolean flag){
    6.         if(root == null)
    7.             return 0;   
    8.         if(root.left == null && root.right ==null && flag)
    9.             return root.val; 
    10.         return sum(root.left,true) + sum(root.right,false);   
    11.     }
    12. }

  • 相关阅读:
    猿创征文｜ 微信小程序开发入门与实战（保姆级文章Ⅲ）
    Linux下的基本指令
    IoC控制反转
    【毕业设计】深度学习卫星遥感图像检测与识别 -opencv python 目标检测
    众佰诚：抖音开通橱窗的要求和流程有什么
    for in 、for of详解
    ElasticSearch Java API的使用
    C++异常
    day33 List接口
    GBase 8d支持的标准
  • 原文地址：https://blog.csdn.net/hushe20202020/article/details/126374021