LeetCode刷题【543】二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

 

示例 :
给定二叉树

          1
         / \
        2   3
       / \     
      4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

 

注意：两结点之间的路径长度是以它们之间边的数目表示。

\n

题解

求最长直径，且这个直径可能不经过root节点，看起来应该是深度搜索。先把深搜模板写出来看下下一步怎么办，定义一个length在不断深搜遍历过程中取到最大的直径的数值。

int length = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        if (root==null){
            return 0;
        }
        dfs(root);
        return length;
    }

    private void dfs(TreeNode node){
        if (node.left!=null){
            dfs(node.left);
        }
        if (node.right!=null){
            dfs(node.right);
        }
        return;
    }

根据题意，当前节点的最大直径的路径为左边最大深度+当前节点+右边最大深度，所以在dfs算法中递归左子树和递归右子树的时候应当取到他们的对应子树的最大深度。那么这个时候改下dfs方法。

private int dfs(TreeNode node){
        int leftHeight = 0;
        int rightHeight = 0;
        if (node.left!=null){
            leftHeight = dfs(node.left);
        }
        if (node.right!=null){
            rightHeight = dfs(node.right);
        }
        return Math.max(rightHeight,leftHeight)+1;
    }

最后当然要return Math.max(rightHeight,leftHeight)+1;取到当前节点下的左子树和右子树中深度更深的那个子树的深度，再加上当前节点的深度+1；

而在这个时候就可以发现，左子树右子树的深度有了，就可以得到经过当前节点的最大直径的长度了，顺便重命名下length为maxLength，只要拿已存的maxLength和当前的maxLength比较得到更大的值重新赋值给maxLength就可以了。

private int dfs(TreeNode node){
        int leftHeight = 0;
        int rightHeight = 0;
        if (node.left!=null){
            leftHeight = dfs(node.left);
        }
        if (node.right!=null){
            rightHeight = dfs(node.right);
        }
        maxLength = Math.max(maxLength,leftHeight+rightHeight+1);
        return Math.max(rightHeight,leftHeight)+1;
    }

跑一下用例

			测试用例:[1,2,3,4,5]
			测试结果:4
			期望结果:3

不大对劲，差在哪里呢？哦

返回 3, 它的长度是路径 [4,2,1,3] 

路径长度应该是节点数减1

最终代码如下

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    int maxLength = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        if (root==null){
            return 0;
        }
        dfs(root);
        return maxLength-1;
    }

    private int dfs(TreeNode node){
        int leftHeight = 0;
        int rightHeight = 0;
        if (node.left!=null){
            leftHeight = dfs(node.left);
        }
        if (node.right!=null){
            rightHeight = dfs(node.right);
        }
        maxLength = Math.max(maxLength,leftHeight+rightHeight+1);
        return Math.max(rightHeight,leftHeight)+1;
    }




}
//leetcode submit region end(Prohibit modification and deletion)