二叉树-路径相关

• 总结
• 快速复习
• • 判断是否存在路径和为target（开胃）
  • 所有和为target的路径（模板）
  • 根到叶数字之和
• 重点
• • 所有节点都可以作为起点（稍有创新）
• 左右贡献类
• • 二叉树中的最大路径和
  • 最长同值路径(还不能做对)
  • 二叉树最长连续序列(重点)
  • • 基础
    • 进阶

原则：有进必有出，有出之前必有进，进了马上出

添加链接描述

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false; // root为null节点
        if (root.left == null && root.right == null) { //root为叶子节点
            if (root.val != targetSum) {
                return false;
            } else
                return true;
        }
          // root为非叶子节点
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

添加链接描述

class Solution {
    List> ans=new ArrayList<>();

    public List> pathSum(TreeNode root, int targetSum) {
        List track = new ArrayList<>();
        dfs(root, targetSum, track);
        return ans;
    }

    private void dfs(TreeNode root, int targetSum,Listtrack) {

        if(root==null)
            return;

        if(root.left==null && root.right==null){
            if(targetSum==root.val){
               //1
                track.add(root.val); //进
                ans.add(new ArrayList<>(track));
                track.remove(track.size()-1); //有进必有出
            }
            return;
        }

        track.add(root.val);//2、 1处进了和我有什么关系？我该进就要进
        dfs(root.left,targetSum-root.val,track);
        // 进入左右分支的 track 是一样的，这里不用写下面两行，因为二者相互抵消。
        //  track.remove(track.size()-1);
        // track.add(root.val);
        dfs(root.right,targetSum-root.val,track);
        track.remove(track.size()-1); //2处进了 这里就出

    }
}

添加链接描述

法一：和上题一模一样
法二：好好想！

class Solution {
    public int sumNumbers(TreeNode root) {
        return dfs(root,0);
    }

    private int dfs(TreeNode root, int sum) {
        if(root==null)
            return 0;
        sum=sum*10+root.val;

        if(root.left==null && root.right==null)
            return sum;
        else
            return dfs(root.left,sum)+dfs(root.right,sum);
    }
}

添加链接描述
现在无非就是每个节点都可以像根节点一样拥有一次计算的权利，那就把每个节点都扔进dfs计算一次，另外解除必须到叶子结点才算数的限制即可。

class Solution {
    int ans=0;
    public int pathSum(TreeNode root, int targetSum) {
        if(root==null){
            return 0;
        }
        dfs(root,targetSum);
        pathSum(root.left,targetSum);
        pathSum(root.right,targetSum);
        return ans;
    }

    private void dfs(TreeNode root, int targetSum) {
        if(root==null){
            return;
        }
        if(targetSum==root.val){
            ans++; 
            //return;//不能返回,想想为什么
        }
        dfs(root.left,targetSum-root.val);
        dfs(root.right,targetSum-root.val);
    }
}

添加链接描述
思路:

定义全局变量maxSum记录最大值

对每一个节点，有两个任务
1、计算以这个节点为根的树的最大路径和，用于更新maxSum
2、返回以这个节点为起点，往下到叶子节点，这之中和最大的一条路径的和（以这个节点为起点，不一定要到叶子），以供这个节点的父节点使用。

举个例子：

比如图中的20节点，
1、计算以这个节点为根的树的最大路径和：20+15+7，更新maxSum
2、返回20+15=35；用于-10节点的计算任务

代码：

class Solution {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        //任务1
        maxSum = Math.max(maxSum, priceNewpath);

        // 任务2
        return node.val + Math.max(leftGain, rightGain);
    }
}

添加链接描述

既然路径长度按边来算，那就始终计算边的个数，计算边的个数，计算边的个数。

class Solution {
    int ans;
    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return  ans;
    }

    private int  dfs(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left=dfs(root.left);
        int right=dfs(root.right);

        //如果左节点值和我相同,那么左节点能给我的贡献就是left+1条边，这个1是左节点和我之间的边，否则就是0
        if(root.left!=null && root.val==root.left.val){
            left++;
        }else {
            left=0;
        }
        if(root.right!=null && root.val==root.right.val){
            right++;
        }else {
            right=0;
        }
        ans=Math.max(ans,left+right);//比较的是边的个数
        return Math.max(left,right); //返回的是这个子树中的边的个数
    }
}

添加链接描述
从下往上dfs，先求出左右子树的贡献，然后根据左右子树和当前节点值的大小关系进行相应的处理。

class Solution {
    int ans;
    public int longestConsecutive(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int dfs(TreeNode root) {
        if(root==null){
            return 0;
        }
        int left=dfs(root.left);
        int right=dfs(root.right);
        //值不满足则贡献为0
        if(root.left!=null && root.left.val!=root.val+1){
            left=0;
        }
        if(root.right!=null && root.right.val!=root.val+1){
            right=0;
        }
        int res=1+Math.max(left,right);
        ans=Math.max(ans,res);
        return res;
    }
}

添加链接描述

class Solution {
    int ans = 1;

    public int longestConsecutive(TreeNode root) {
        dfs(root);
        return ans;
    }

    private int[] dfs(TreeNode root) {
        if (root == null) {
            return new int[]{0,0};
        }

        int inc=1,dec=1; //自己算一个
        //算出左子树的贡献
        if (root.left != null) {
            int[] left = dfs(root.left);
            if (root.left.val == root.val + 1) {
                inc=left[0]+1;
            }
            if (root.left.val == root.val - 1) {
                dec=left[1]+1;
            }
        }
        //算出右子树的贡献并顺便取左右最大
        if (root.right != null) {
            int[] right = dfs(root.right);
            if (root.right.val == root.val + 1) {
              inc=Math.max(inc,right[0]+1);
            }
            if (root.right.val == root.val - 1) {
                dec=Math.max(dec,right[1]+1);
            }
        }
        ans = Math.max(ans, inc+dec-1);
        return new int[]{inc,dec};
    }
}