算法

二叉树的直径

2020-10-27  本文已影响0人  小鱼嘻嘻

问题1

二叉树的最大直径

原理

代码

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

二叉树的最大路径和

原理

代码

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;
    }
    
}

注意事项

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

上一篇下一篇

猜你喜欢

热点阅读