LeetCode 有关树深度、路径的题目（JAVA代码实现）

傷城~ 2021-09-22 16:02 237阅读 0赞

### 文章目录 ###

*  1. 路径相关的题目
 *   *  112.路径总和
     *  113.路径总和 II
     *  437.路径总和 III
     *  124.二叉树中的最大路径和
     *  257.二叉树的所有路径
 *  2. 深度相关的题目
 *   *  111.二叉树的最小深度
     *  559.N叉树的最大深度
     *  865.具有所有最深结点的最小子树
 *  3. 其他长度相关的题目
 *   *  543.二叉树的直径
     *  563.二叉树的坡度
     *  662.二叉树最大宽度

# 1. 路径相关的题目 #

## 112.路径总和 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]  
题目：判断是否存在从根节点到某一叶子节点的路径，路径上所有节点值之和为给定值  
思路：利用深度优先算法

public boolean hasPathSum(TreeNode root, int sum) { 
            // 对题目的输入进行判断，若空则返回
            return root != null && hasPathSum1(root, sum);
        }
    
        /* * 两种情况： * ① 当前节点为叶子节点，且符合要求 * ② 当前节点为内部节点，判断其孩子节点中是否有符合要求的题目 * */
        private static boolean hasPathSum1(TreeNode root, int sum) { 
            return (root.val == sum && root.left == null && root.right == null)
                    || (root.left != null && hasPathSum1(root.left, sum - root.val))
                    || (root.right != null && hasPathSum1(root.right, sum - root.val));
        }
    
        // 下面有另一种书写方式:
        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);
        }

复杂度：

*  时间复杂度：O(n)，为最糟糕的情况，即遍历了所有节点，但没有一个路径符合
 *  空间复杂度：O(log(n))，为树的高度，最多有几个节点被压入栈中

## 113.路径总和 II ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 1]  
题目：类似于上一道题，但这里要求是输出所有符合要求的路径  
思路：依旧是深度优先遍历，但要遍历完所有路径，相同的思路两种代码的写法：

// 写法一：
        public List<List<Integer>> pathSum(TreeNode root, int sum) { 
            List<List<Integer>> lists = new ArrayList<>();
            if (root == null) return lists;
            pathSum(root, sum, lists, new ArrayList<>());
            return lists;
        }
    
        private void pathSum(TreeNode root, int sum, List<List<Integer>> lists, List<Integer> list){ 
            if (root == null) { 
                return;
            }
            list.add(root.val);
            // 判断为从 root-to-leaves 的串，则判断是否符合题意
            if (root.val == sum && root.left == null && root.right == null) { 
                lists.add(new ArrayList<>(list));
            } else { 
                // 当前节点为中间节点，则继续往下查看其左右节点
                pathSum(root.left, sum - root.val, lists, list);
                pathSum(root.right, sum - root.val, lists, list);
            }
            // 完成这个节点的遍历返回父节点时，要删除当前节点的值
            list.remove(list.size() - 1);
        }
    
    	// 写法二：
    	public List<List<Integer>> pathSum(TreeNode root, int sum) { 
            List<List<Integer>> lists = new ArrayList<>();
            if (root == null) { 
                return lists;
            }
            helper(new ArrayList<>(), sum, root, lists);
            return lists;
        }
    
        private void helper(List<Integer> list, int sum, TreeNode root, List<List<Integer>> lists) { 
            if (root.left == null && root.right == null) { 
                if (sum == root.val) { 
                    list.add(root.val);
                    lists.add(new ArrayList<>(list));
                    list.remove(list.size() - 1);
                }
                return;
            }
    
            if (root.left != null) { 
                list.add(root.val);
                helper(list, sum - root.val, root.left, lists);
                list.remove(list.size() - 1);
            }
    
            if (root.right != null) { 
                list.add(root.val);
                helper(list, sum - root.val, root.right, lists);
                list.remove(list.size() - 1);
            }
        }

复杂度：

*  时间复杂度：O(n)，遍历了所有的节点

## 437.路径总和 III ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 2]  
题目：对于任意从顶向下的路径，计算所有和为给定值的路径  
思路：遍历整个二叉树，将所有节点都作为一次根节点，每次遍历从新定义的根节点开始，判断往下到某个节点时，是否有路径和为给定值的情况

// 遍历所有节点作为根节点的情况
        public int pathSum(TreeNode root, int sum) { 
            if (root == null) return 0;
            return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
        }
    
        // 将某个点作为根节点的所有路径符合要求的数目
        private static int pathSumFrom(TreeNode node, int sum) { 
            if (node == null) return 0;
            return (node.val == sum ? 1 : 0)
                    + pathSumFrom(node.left, sum - node.val) + pathSumFrom(node.right, sum - node.val);
        }

复杂度：

*  时间复杂度：O(n²)，两次遍历

## 124.二叉树中的最大路径和 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 3]  
题目：二叉树中任意路径的最大和  
思路：

// 最大值
        int max = Integer.MIN_VALUE;
    
        public int maxPathSum(TreeNode root) { 
            if (root == null) return 0;
            helper(root);
            return max;
        }
    
        private int helper(TreeNode root) { 
            if (root == null) return 0;
            // 分别求出能从左右子树中获得的最大值，如果为负，则抛弃子树
            int left = Math.max(0, helper(root.left));
            int right = Math.max(0, helper(root.right));
            // 比较包含这个根节点的最大值路径跟 max的大小
            max = Math.max(max, left + right + root.val);
            return Math.max(left, right) + root.val;
        }

复杂度：

*  时间复杂度：O(n)，遍历了一次所有节点
 *  空间复杂度：O(log(n))

## 257.二叉树的所有路径 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 4]  
题目：输出所有路径  
思路：深度优先遍历

private static List<String> binaryTreePaths1(TreeNode root) { 
            List<String> lists = new ArrayList<>();
            if (root == null) return lists;
            helper(root, "" + root.val, lists);
            return lists;
        }
    
        private static void helper(TreeNode root, String path, List<String> lists) { 
            if (root == null) return;
            if (root.left == null && root.right == null) { 
                lists.add(path);
                return;
            }
            if (root.left != null) { 
                helper(root.left, path + "->" + root.left.val, lists);
            }
            if (root.right != null) { 
                helper(root.right, path + "->" + root.right.val, lists);
            }
        }

复杂度：

*  时间复杂度：O(n)

# 2. 深度相关的题目 #

## 111.二叉树的最小深度 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 5]  
题目：求给定二叉树从根节点到叶子节点最短的路径长度  
思路：比较两个子节点哪个获得了较小的深度，加1并返回

public int minDepth(TreeNode root) { 
            if (root == null)  return 0;
            int leftMinDepth = minDepth(root.left);
            int rightMinDepth = minDepth(root.right);
            // 左子树不存在
            if (leftMinDepth == 0) { 
                return rightMinDepth + 1;
            }
            // 右子树不存在
            if (rightMinDepth == 0) { 
                return leftMinDepth + 1;
            }
            return leftMinDepth > rightMinDepth? rightMinDepth + 1: leftMinDepth + 1;
        }

复杂度：

*  时间复杂度：O(n)，遍历整个二叉树
 *  空间复杂度：O(log(n))

## 559.N叉树的最大深度 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 6]  
题目：求N叉树的最大深度  
思路：

public int maxDepth(Node root) { 
            if (root == null) { 
                return 0;
            }
            int max = 0;
            for (Node childNode : root.children
                 ) { 
                int value = maxDepth(childNode);
                if (value > max) { 
                    max = value;
                }
            }
            return max + 1;
        }

复杂度：

*  时间复杂度：O(n)
 *  空间复杂度：O(log(n))

## 865.具有所有最深结点的最小子树 ##

![20181227170149962.png][]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 7]  
题目：寻找一个最小的子树，可以包括所有的最深节点  
思路：从根部开始，当某个节点的左右子树深度相同时，则该节点包含了所有最大深度的子节点

public TreeNode subtreeWithAllDeepest(TreeNode root) { 
            if (root == null) return null;
            if (depth(root.left) == depth(root.right)) { 
                return root;
            } else { 
                if (depth(root.left) > depth(root.right)) { 
                    return subtreeWithAllDeepest(root.left);
                } else { 
                    return subtreeWithAllDeepest(root.right);
                }
            }
        }
    
        // 计算深度，这里可以用 map 进行优化，先行记录深度
        private static int depth(TreeNode root) { 
            if (root == null) return 0;
            int leftDepth = depth(root.left);
            int rightDepth = depth(root.right);
            return leftDepth > rightDepth? leftDepth + 1: rightDepth + 1;
        }

# 3. 其他长度相关的题目 #

## 543.二叉树的直径 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 8]  
题目：求二叉树中的最长路径，无需一定要通过根节点  
思路：

private static int diameterOfBinaryTree(TreeNode root) { 
            if (root == null) return 0;
            Map<TreeNode, Integer> map = new HashMap<>();
            buildDepthMap(root, map);
            map.put(null, 0);
            // 因为算的是 edge，并不是算点数
            return diameterOfBinaryTree(root, map) - 1;
        }
    
        // 需求最长路径长度
        private static int diameterOfBinaryTree(TreeNode root, Map<TreeNode, Integer> map) { 
            if (root == null) return 0;
            int withTheRoot = map.get(root.left) + map.get(root.right) + 1;
            int left = diameterOfBinaryTree(root.left, map);
            int right = diameterOfBinaryTree(root.right, map);
            return Math.max(withTheRoot, Math.max(left, right));
        }
        
        // 对 Map 进行填充
        private static int buildDepthMap(TreeNode root, Map<TreeNode, Integer> map) { 
            if (root == null) return 0;
            int depth = 1 + Math.max(buildDepthMap(root.left, map), buildDepthMap(root.right, map));
            map.put(root, depth);
            return depth;
        }
    
    
        // 解法二：使用全局变量
        int max = 0;
        public int diameterOfBinaryTree2(TreeNode root) { 
            helper(root);
            return max;
        }
    
        public int helper(TreeNode root){ 
            if (root == null)return 0;
            int left = helper(root.left);
            int right = helper(root.right);
            max = Math.max(max, left + right);
            return Math.max(left, right) + 1;
        }

## 563.二叉树的坡度 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 9]  
题目：求所有节点的坡度和（坡度：节点的左子树值的和与右子树值的和的绝对值）  
思路：设置全局变量，遍历所有节点

// 最终的结果
        int result = 0;
        public int findTilt(TreeNode root) { 
            helper(root);
            return result;
        }
        private int helper(TreeNode root) { 
            if (root == null) return 0;
            int leftValue = helper(root.left);
            int rightValue = helper(root.right);
            // 将该节点的左子树之和与右子树节点之和做绝对值
            result += Math.abs(leftValue - rightValue);
            // 这里要返回当前树的节点和，所以是其左右子树，再加上节点的value
            return leftValue + rightValue + root.val;
        }

复杂度：

*  时间复杂度：O(n)
 *  空间复杂度：O(log(n))

## 662.二叉树最大宽度 ##

![20181227231116598.png][]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 11]  
题目：求每一层中最左右两个节点之间最远距离  
思路：由于所求考虑的节点，都是在同一层中，所以我考虑的是用层序遍历，将每一层拆出来单独考虑。第二个问题就是如何计算距离的问题，我们可以用数组来存满二叉树，其中，如果根节点为下标为n，其左子节点为2\*n+1，右子节点为2\*n+2，我们可以利用这个特点，利用一个LinkedList来存下标值，并对每一层保存的下标值，取最左一个跟最右一个进行比较，即为该层可获得的最大举例

public int widthOfBinaryTree1(TreeNode root) { 
            if (root == null) return 0;
            if (root.left == null && root.right == null) return 1;
            // 用队列进行层序遍历
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            // 将每一次遍历的节点的下标进行保存
            LinkedList<Integer> list = new LinkedList<>();
            list.add(0);
            TreeNode cur = null;
            int num = 0, index = 0, max = Integer.MIN_VALUE;
            while (!queue.isEmpty()) { 
                num = queue.size();
                for (int i = 0; i < num; i++) { 
                    cur = queue.poll();
                    index = list.getFirst();
                    if (cur.left != null) { 
                        queue.add(cur.left);
                        list.add(2 * index + 1);
                    }
                    if (cur.right != null) { 
                        queue.add(cur.right);
                        list.add(2 * index + 2);
                    }
                    // 清除当前节点的下标值
                    list.remove(0);
                }
                // 通过最左右的两个节点的下标值，来求宽度
                if (!list.isEmpty()) { 
                    max = Math.max(max, list.get(list.size() - 1) - list.getFirst()+ 1);
                }
            }
            return max;
        }

其他 LeetCode JAVA代码：  
https://github.com/Parallelline1996/LeetCode/tree/master

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/26db3253b09941088b74fcc1ee641fe0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 1]: /images/20210920/21c0fd9cd9b14212af2136b9d2fd2c8f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 2]: /images/20210920/349cc9d6d4e34c42960a14028ca0ce32.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 3]: /images/20210920/fa22377b7e3c44d6a089d914cd36eff2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 4]: /images/20210920/e1077414249d4490b32775142919c61c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 5]: /images/20210920/e318fe43e3b34d7c87e756e09f1d2580.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 6]: /images/20210920/8a6b2dbcca33465c99afe75bb79a5dc8.png
[20181227170149962.png]: /images/20210920/53d87df24f7444579c1282999a293769.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 7]: /images/20210920/3fabf3ad39c34edab136d12d18af4526.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 8]: /images/20210920/c30946efcfd14216b2e65c861c54b51d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 9]: /images/20210920/b277ee2d711248bbb0948a04468ca446.png
[20181227231116598.png]: /images/20210920/0a8210a94a8a4312a3c40199d7944cff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 10]: /images/20210920/82ef884f8f564cca9e418c88ba8e8393.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 11]: /images/20210920/75604812041e4f44a30f08e9c3312b1c.png