LeetCode-543-二叉树的直径

题目

思路

1. 感觉这个不会用递归做…果然是太久没写题了，简单题都没思路了。
2. 找出把每一个节点作为根节点的直径长度然后求最大值？确实是这个思路，通过了。

代码

    int ans=Integer.MIN_VALUE;
    public int diameterOfBinaryTree(TreeNode root) {
    
        if(root.left==null && root.right==null) return 0;
        //无意义 占位符号
        int flag=DFS(root);
        return ans;

    }
    public int DFS(TreeNode root){
    
        //把当前节点作为根节点 如果走到叶子节点了 说明以当前节点为根节点的直径为0 但将其作为一边 则返回1
        if(root.left==null && root.right==null) return 1;
        //否则计算
        int leftval=0,rightval=0;
        if(root.left!=null)  leftval = DFS(root.left);
        if(root.right!=null) rightval = DFS(root.right);
        if(leftval+rightval>ans) {
    
            ans=leftval+rightval;
        }
        //同理返回两边中的最大值+1
        return Math.max(leftval,rightval)+1;
    }