mzoe666888

V1

2022/04/07阅读:17主题:兰青

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

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

欢迎关注《内卷学苑》[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为头的树,分析可能性

  1. 和X无关

    • X左树上的最大值
    • X右树上的最大值
  2. 和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为头的树,分析可能性

  1. 和X无关

    • X左树上的最大值
    • X右树上的最大值
  2. 和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(01);
    // 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/

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1