樹的遞歸專題

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