二叉树的直径

问题1

二叉树的最大直径

原理

• 首先，需要定义一个变量记录二叉树的直径
• 其次，递归遍历，找到每一层二叉树的
• 递归的终止条件为，当前节点为空返回0

代码

class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
      
      max(root);
      return max;
    }

    private int max(TreeNode root){
        if(root==null){
            return 0;
        }
        int left = max(root.left);
        int right  = max(root.right);
        max = Math.max(max,left+right);

        return Math.max(left,right)+1;
    }

}

注意事项

• 需要使用临时遍历记录最大路径

问题2

二叉树的最大路径和

原理

• 递归找到左侧路径的最大值，找到右侧路径的最大值
• 比较当前left+right+root.val 和历史最大值的大小
• 返回当前层的最大值

代码

class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
      max(root);
      return max;
    }

    private int max(TreeNode root){
        if(root==null){
            return 0;
        }
        int left = 0;
        if(root.left!=null){
            left = Math.max(left,max(root.left));
        }
        int right = 0;
        if(root.right!=null){
            right = Math.max(right,max(root.right));
        }
        max = Math.max(max,left+right+root.val);

        return Math.max(left,right)+root.val;
    }
    
}

注意事项

** 需要使用临时遍历记录最大路径之和