LeetCode——树：递归

冷不防 2023-07-05 13:10 53阅读 0赞

# LeetCode——树：递归 #

--------------------

## 目录 ##

1.  概述
2.  树的高度（LeetCode104）
3.  平衡树（LeetCode110）
4.  两节点的最长路径（LeetCode543）
5.  翻转树（LeetCode226）
6.  归并两棵树（LeetCode617）
7.  判断路径和是否等于一个数（LeetCode112）
8.  统计路径和等于一个数的路径数量（LeetCode437）
9.  子树（LeetCode572）
10. 树的对称（LeetCode101）
11. 最小深度（LeetCode111）
12. 统计左叶子节点的和（LeetCode404）
13. 相同节点值的最大路径长度（LeetCode687）
14. 间隔遍历（LeetCode337）
15. 小结

--------------------

### 0. 概述 ###

1.  一棵树要么是空树，要么有两个指针，每个指针指向一棵树。树是一种递归结构，很多树的问题可以使用递归来处理

--------------------

### 1. 树的高度（LeetCode104） ###

##### 1. 概述 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]

##### 2. 思路 #####

1.  利用递归，可以遍历完全部节点（压入栈再取出），就可以计算高度
2.  就是假設可以获取左节点高度：int left = maxDepth(root.left);
3.  可以获取右节点高度：int right = maxDepth(root.right);
4.  返回的是root层的高度：即左右节点中高的值加1

##### 3. 代码 #####

public static int maxDepth1(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            return Math.max(left, right) + 1;
        }

--------------------

### 2. 平衡树（LeetCode110） ###

##### 1. 思路 #####

1.  利用递归，计算左右子树最大高度差，如果超过1，则返回false。递归是从下面的节点往上遍历的

##### 2. 代码 #####

private static boolean result = true;
    
        public static boolean isBalanced(TreeNode root) {
            maxDepth(root);
            return result;
        }
    
        private static int maxDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int l = maxDepth(root.left);
            int r = maxDepth(root.right);
            if (Math.abs(l - r) > 1) {
                result = false;
            }
            return Math.max(l, r) + 1;
        }

--------------------

### 3. 两节点的最长路径（LeetCode543） ###

##### 1. 概述 #####

![在这里插入图片描述][20200215092742849.png]

##### 2. 思路 #####

1.  利用递归，可以求出左右子树的高度，加起来的结果中的最大值即为最长路径
2.  返回的结果是本层需要返回的结果，而不是和。

##### 3. 代码 #####

private static int max = 0;
    
        public static int diameterOfBinaryTree(TreeNode root) {
            maxDepth(root);
            return max;
        }
    
        private static int maxDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int l = maxDepth(root.left);
            int r = maxDepth(root.right);
            max = Math.max(max, l + r);
            return Math.max(l, r) + 1;
        }

--------------------

### 4. 翻转树（LeetCode226） ###

##### 1. 概述 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]

##### 2. 思路 #####

1.  利用递归，递归会遍历所有的节点，然后交换当前root的左右节点，从下一层一层往上，就会整体交换

##### 3. 代码 #####

public static 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;
        }

--------------------

### 5. 归并两棵树（LeetCode617） ###

##### 1. 概述 #####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]

##### 2. 思路 #####

1.  对两棵树同时进行前序遍历，并将对应的节点进行合并
2.  在遍历时，如果两棵树的当前节点均不为空，就将它们的值相加，并对它们的左孩子和右孩子进行递归合并；
3.  如果其中有一棵树为空，那么就返回另一棵树作为结果。如果两棵树均为空，此时返回任意一棵树均可（因为都为null）

##### 3. 代码 #####

public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
            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;
        }

--------------------

### 6. 判断路径和是否等于一个数（LeetCode112） ###

##### 1. 概述 #####

1.  给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 3]

##### 2. 思路 #####

1.  利用递归，遍历整棵树
2.  如果当前节点不是叶子节点，对它的所有孩子节点，递归调用hasPathSum函数，其中sum值减去当前节点的权值
3.  如果当前节点为叶子节点，检查sum值是否为0，也就是是否找到了给定的目标值

##### 3. 代码 #####

public static boolean hasPathSum(TreeNode root, int sum){
            if (root==null){
                return false;
            }
            sum -= root.val;
            if (root.left==null&&root.right==null){
                return sum==0;
            }
            return hasPathSum(root.left,sum)||hasPathSum(root.right,sum);
        }

--------------------

### 7. 统计路径和等于一个数的路径数量（LeetCode437） ###

##### 1. 概述 #####

1.  给定一个二叉树，它的每个结点都存放着一个整数值。找出路径和等于给定数值的路径总数。路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

##### 2. 思路 #####

1.  利用递归可以遍历树的每个节点，从每个节点出发，寻找是否有等于sum的值，如果有，次数加1
2.  总数ret=pathSumStartWithRoot(root, sum)（从root出发，是否等于sum）+ pathSum(root.left, sum)+pathSum(root.right, sum)（遍历其他节点）
3.  pathSumStartWithRoot(root, sum)：创建ret变量记录路径和=sum 的次数，如果root.val=sum，说明找到了要求的路径和，ret++，否则再向它左右节点遍历，看是否符合要求

##### 3. 代码 #####

public static int pathSum(TreeNode root, int sum) {
            if (root == null) {
                return 0;
            }
            return pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
        }
    
        private static 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;
        }

--------------------

### 8. 子树（LeetCode572） ###

##### 1. 概述 #####

1.  给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 4]

##### 2. 思路 #####

1.  利用递归，return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
    
    1.  isSubtreeWithRoot(s, t)：用于判断两个子树是否相等  
        1. 如果tnull&&snull，return true  
        2. 如果tnull||snull，return false  
        3. 如果t.val!=s.val，return false  
        4. 再比较它们的左右节点是否相同
    2.  如果t不是当前节点s的子树，则跳到s的左孩子或者右孩子继续比较

##### 3. 代码 #####

public static boolean isSubtree(TreeNode s, TreeNode t) {
            if (s == null && t == null) {
                return true;
            }
            if (s == null) {
                return false;
            }
            return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
        }
    
        private static boolean isSubtreeWithRoot(TreeNode s, TreeNode t) {
            if (s == null && t == null) {
                return true;
            }
            if (s == null || t == null) {
                return false;
            }
            if (t.val != s.val) {
                return false;
            }
            return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);
        }

--------------------

### 9. 树的对称（LeetCode101） ###

##### 1. 概述 #####

1.  给定一个二叉树，检查它是否是镜像对称的。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 5]

##### 2. 思路 #####

1.  利用递归，首先判断两个节点是否相同，不相同返回false，然后对子节点进行递归。s的左孩子对应t的右孩子，s的右孩子对应t的左孩子

##### 3. 代码 #####

public static boolean isSymmetric(TreeNode root) {
            if (root == null) {
                return true;
            }
            return isSymmetric(root.left, root.right);
        }
    
        public static boolean isSymmetric(TreeNode t1, TreeNode t2) {
            if (t1 == null && t2 == null)
                return true;
            if (t1 == null || t2 == null)
                return false;
            if (t1.val != t2.val)
                return false;
            return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
        }

--------------------

### 10. 最小深度（LeetCode111） ###

##### 1. 概述 #####

1.  给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

##### 2. 思路 #####

1. 利用递归，假设可以得到root的左右孩子的高度，那么最小深度就是左右孩子高度较小的那个加上自身高度，即return Math.min(left, right)+1
    		2. 而root的左右孩子也能看出一颗完整的树，有自己左右孩子高度，依次递归
    		3. 当左右孩子为null时，高度就是自己。当左右孩子有一个为null时，高度就是不为null的高度加上自己。即if(left==0||right==0) return left+right+1

##### 3. 代码 #####

public static int minDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int left = minDepth(root.left);
            int right = minDepth(root.right);
            if (left == 0 || right == 0) {
                return left + right + 1;
            }
            return Math.min(left, right) + 1;
        }

--------------------

### 11. 统计左叶子节点的和（LeetCode404） ###

##### 1. 概述 #####

1.  计算给定二叉树的所有左叶子之和。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 6]

##### 2. 思路 #####

1.  利用递归，每一个非叶节点都可以构成一棵树，假设当前节点为root，判断是否有左孩子，如果有，值相加，继续跳到root.right遍历。
2.  如果当前root节点左孩子不是叶子节点，就跳到它的左孩子和右孩子继续遍历
3.  也就是说利用递归遍历全部节点，当遇到左叶子节点就停下来相加，否则继续遍历

##### 3. 代码 #####

public static 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 static boolean isLeaf(TreeNode node) {
            if (node == null)
                return false;
            return node.left == null && node.right == null;
        }

--------------------

### 12. 相同节点值的最大路径长度（LeetCode687） ###

##### 1. 概述 #####

1.  给定一个二叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 7]  
    ![在这里插入图片描述][20200215100632524.png]

##### 2. 思路 #####

1.  利用递归，可以遍历全部节点，从下到上。
2.  int left = dfs(root.left)，假设能获取到左节点的最长同值长度  
    int right = dfs(root.right)，能获取到右节点最长同值长度
3.  再判断和root节点是否相同，root.left!=null并且root.left.val==root.val，即相同的话左节点最长长度为当前长度加1，右节点同理。最长长度=Math.max(path, leftPath+rightPath)
4.  最后返回左右节点较长的一边

##### 3. 代码 #####

private static int path = 0;
    
        public static int longestUnivaluePath(TreeNode root) {
            dfs(root);
            return path;
        }
    
        private static 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.left.val == root.val ? left + 1 : 0;
            int rightPath = root.right != null && root.right.val == root.val ? right + 1 : 0;
            path = Math.max(path, leftPath + rightPath);
            return Math.max(leftPath, rightPath);
        }

--------------------

### 13. 间隔遍历（LeetCode337） ###

##### 1. 概述 #####

1.  小偷发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
2.  计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

##### 2. 思路 #####

1.  root为根节点时，抢劫的金额有两种可能  
    1. 如果算上root本身的值root.val，如果左子树不为null，则再加上左子树左右节点的值，右子树同理。  
    2. 如果不算上root本身的值，则是rob(root.left)+rob(root.right)的值  
    3. rob函数表示以当前节点为根，能抢到最大的值

##### 3. 代码 #####

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

--------------------

### 14. 小结 ###

1.  首先，要清楚，递归可以遍历所有树的节点，比如:  
    int left = minDepth(root.left);  
    int right = minDepth(root.right);
2.  所有，我们要关心的就是怎么对结果加工，比如求最小深度，那节点为null返回什么，一个为null返回什么，两个为null返回什么

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200215091720151.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[20200215092742849.png]: https://img-blog.csdnimg.cn/20200215092742849.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200215093109156.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020021509335183.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200215093734304.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200215094636431.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200215094956475.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200215100046451.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200215100616574.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA==,size_16,color_FFFFFF,t_70
[20200215100632524.png]: https://img-blog.csdnimg.cn/20200215100632524.png