内卷大厂系列《二叉树路径和问题五连击》

vlambda
2022-04-11

内卷大厂系列《二叉树路径和问题五连击》

大厂高频算法面试题：《二叉树路径和系列》，主要分为最大路径和与路径和问题，您将学到如何利用二叉树的递归套路模型来解决，只需要罗列可能性，把可能性罗列清楚，写代码形如行云流水般的顺利。

欢迎关注《内卷学苑》^[1]

一、二叉树最大路径和I

给定一个二叉树的头节点head，路径必须是头节点出发，到叶节点为止，返回最大路径和

1、分析

方法一：定义一个全局maxSum最大路径和变量，初始值为Integer.Min_VALUE，只有头节点出发沿途路径累加起来传下去，到达叶节点时才更新maxSum值

方法二：利用二叉树的递归套路模型，因为题目要求必须从头节点出发，罗列可能性只有一种，和X有关，从头节点出发

2、实现

2.1、方法一

public static class Node {
    public int value;
    public Node left;
    public Node right;

    public Node(int val) {
        value = val;
    }
}

public static int maxSum = Integer.MIN_VALUE;

public static int maxPath(Node head) {
    maxSum = Integer.MIN_VALUE;
    process(head, 0);
    return maxSum;
}

// 之前的路径和，为pre
public static void process(Node x, int pre) {
    if (x.left == null && x.right == null) {
        maxSum = Math.max(maxSum, pre + x.value);
    }
    if (x.left != null) {
        p(x.left, pre + x.value);
    }
    if (x.right != null) {
        p(x.right, pre + x.value);
    }
}

2.2、方法二

public static class Node {
    public int value;
    public Node left;
    public Node right;

    public Node(int val) {
        value = val;
    }
}

// x为头的整棵树上，最大路径和是多少，返回。
// 路径要求，一定从x出发，到叶节点，算做一个路径
public static int maxPath(Node x) {
    if (x.left == null && x.right == null) {
        return x.value;
    }
    int next = Integer.MIN_VALUE;
    if (x.left != null) {
        next = maxPath(x.left);
    }
    if (x.right != null) {
        next = Math.max(next, maxPath(x.right));
    }
    return x.value + next;
}

二、二叉树最大路径和II

给定一个二叉树的头节点head，路径可以从任何节点出发，但必须往下走到达任何节点，返回最大路径和

1、分析

利用二叉树的递归套路模型，以X为头的树，分析可能性

和X无关

X左树上的最大值
X右树上的最大值

和X有关

只有X自己就是最大值
从X出发往左树走
从X出发往右树走

提取信息属性：allTreeMaxSum（树上最大值），fromHeadMaxSum（从头出发最大值）

2、实现

public static int maxSum(Node head) {
    if (head == null) {
        return 0;
    }
    return process(head).allTreeMaxSum;
}

public static class Info {
    public int allTreeMaxSum;
    public int fromHeadMaxSum;

    public Info(int all, int from) {
        allTreeMaxSum = all;
        fromHeadMaxSum = from;
    }
}

// 1）X无关的时候， 1， 左树上的整体最大路径和 2， 右树上的整体最大路径和
// 2) X有关的时候 3， x自己 4， x往左走 5，x往右走
public static Info process(Node x) {
    if (x == null) {
        return null;
    }
    Info leftInfo = process(x.left);
    Info rightInfo = process(x.right);
    int p1 = Integer.MIN_VALUE;
    if (leftInfo != null) {
        // 可能性一
        p1 = leftInfo.allTreeMaxSum;
    }
    int p2 = Integer.MIN_VALUE;
    if (rightInfo != null) {
        // 可能性二
        p2 = rightInfo.allTreeMaxSum;
    }
    // 可能性三
    int p3 = x.value;
    // 可能性四
    int p4 = Integer.MIN_VALUE;
    if (leftInfo != null) {
        p4 = x.value + leftInfo.fromHeadMaxSum;
    }
    // 可能性五
    int p5 = Integer.MIN_VALUE;
    if (rightInfo != null) {
        p5 = x.value + rightInfo.fromHeadMaxSum;
    }
    int allTreeMaxSum = Math.max(Math.max(Math.max(p1, p2), p3), Math.max(p4, p5));
    int fromHeadMaxSum = Math.max(Math.max(p3, p4), p5);
    return new Info(allTreeMaxSum, fromHeadMaxSum);
}

三、二叉树最大路径和III

路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点。

路径和是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其最大路径和。

示例 1：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

示例 2：

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

leetcode^[2]

1、分析

可以从任何节点出发，比二叉树最大路径和II多了一种可能性

利用二叉树的递归套路模型，以X为头的树，分析可能性

和X无关

X左树上的最大值
X右树上的最大值

和X有关

只有X自己就是最大值
从X出发往左树走
从X出发往右树走
从左树出发，经过X，到大右树

提取信息属性：allTreeMaxSum（树上最大值），fromHeadMaxSum（从头出发最大值）

2、实现

public static class TreeNode {
    public int val;
    public Node left;
    public Node right;

    public Node(int val) {
        val = val;
    }
}

public static class Info {
    public int allTreeMaxSum;
    public int fromHeadMaxSum;

    public Info(int all, int from) {
        allTreeMaxSum = all;
        fromHeadMaxSum = from;
    }
}

public static int maxPathSum(TreeNode head) {
    if (head == null) {
        return 0;
    }
    return process(head).allTreeMaxSum;
}

// 1）X无关的时候， 1， 左树上的整体最大路径和 2， 右树上的整体最大路径和
// 2) X有关的时候 3， x自己 4， x往左走 5，x往右走 6, 既往左，又往右
public static Info process(TreeNode x) {
    if (x == null) {
        return null;
    }
    Info leftInfo = process(x.left);
    Info rightInfo = process(x.right);
    int p1 = Integer.MIN_VALUE;
    if (leftInfo != null) {
        // 可能性一
        p1 = leftInfo.allTreeMaxSum;
    }
    int p2 = Integer.MIN_VALUE;
    if (rightInfo != null) {
        // 可能性二
        p2 = rightInfo.allTreeMaxSum;
    }
    // 可能性三
    int p3 = x.val;
    int p4 = Integer.MIN_VALUE;
    if (leftInfo != null) {
        // 可能性四
        p4 = x.val + leftInfo.fromHeadMaxSum;
    }
    int p5 = Integer.MIN_VALUE;
    if (rightInfo != null) {
        // 可能性五
        p5 = x.val + rightInfo.fromHeadMaxSum;
    }
    int p6 = Integer.MIN_VALUE;
    if (leftInfo != null && rightInfo != null) {
        // 可能性六
        p6 = x.val + leftInfo.fromHeadMaxSum + rightInfo.fromHeadMaxSum;
    }
    int allTreeMaxSum = Math.max(Math.max(Math.max(p1, p2), p3), Math.max(Math.max(p4, p5), p6));
    int fromHeadMaxSum = Math.max(Math.max(p3, p4), p5);
    return new Info(allTreeMaxSum, fromHeadMaxSum);
}

四、二叉树路径和问题IV

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的路径的数目。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

leetcode^[3]

1、分析

在二叉树上求累加和问题，题目要求只能从父节点到子节点，路径方向必须只能向下，以头的节点出发，往下走，联想到二叉树的先序遍历顺序就是（头、左、右），所以在先序遍历的基础思路上靠

准备一个Map，key为当前路径累加和，value为出现的次数

2、实现

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
}

public static int pathSum(TreeNode root, int sum) {
    HashMap<Integer, Integer> preSumMap = new HashMap<>();
    preSumMap.put(0, 1);
    // preAll：之前的累加和
    return process(root, sum, 0, preSumMap);
}

// 返回方法数，先序遍历
public static int process(TreeNode x, int sum, int preAll, HashMap<Integer, Integer> preSumMap) {
    if (x == null) {
        return 0;
    }
    int all = preAll + x.val;
    int ans = 0;
    // 以x.val结尾的路径有没有
    if (preSumMap.containsKey(all - sum)) {
        ans = preSumMap.get(all - sum); // 当前值
    }
    if (!preSumMap.containsKey(all)) {
        preSumMap.put(all, 1);
    } else {
        preSumMap.put(all, preSumMap.get(all) + 1);
    }
    // 左树值
    ans += process(x.left, sum, all, preSumMap);
    // 右树值
    ans += process(x.right, sum, all, preSumMap);
    if (preSumMap.get(all) == 1) { // 清理map
        preSumMap.remove(all);
    } else {
        preSumMap.put(all, preSumMap.get(all) - 1);
    }
    return ans;
}

五、二叉树路径和问题V

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

叶子节点是指没有子节点的节点。

示例 1：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

示例 2：

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。

示例 3：

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

leetcode^[4]

1、分析

如果当前节点是叶子节点，只需要判断当前节点是否等于sum，如果当前节点不是叶子节点，则左树上是否满足条件或者右树上是否满足条件

2、实现

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

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

参考资料

[1]

《内卷学苑》: https://mzoe666888.cn

[2]

leetcode: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

[3]

leetcode: https://leetcode-cn.com/problems/path-sum-iii/

[4]

leetcode: https://leetcode-cn.com/problems/path-sum/

vlambda博客
学习文章列表