树的递归专题

leetcode 543. 二叉树的直径

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

示例 :
给定二叉树

          1
         / \
        2   3
       / \     
      4   5    

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

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

由题意可知：一个节点的最大直径 = 它左树的高度 +  它右树的高度

因此本题遍历每个节点，找出所有节点中的直径的最大值即可。

刚开始这么写的

private int max = 0;
    
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = depth(root.left);
        int right = depth(root.right);
        max = max > (left + right) ? max : (left + right);
        diameterOfBinaryTree(root.left);
        diameterOfBinaryTree(root.right);
        return max;

    }

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

但是发现效率不高。仔细想了一下，造成效率不高的原因主要是这么写其实进行了两次遍历。
其实我们在求每个节点的高度的时候，顺带就可以求出其直径，第二种方式代码如下。

 public int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return max;
    }

    private int depth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftDep = depth(root.left);
        int rightDep = depth(root.right);
        max = max > (leftDep + rightDep) ? max : (leftDep + rightDep);
        return (leftDep > rightDep ? leftDep : rightDep) + 1;
    }