Java实现 LeetCode 543 二叉树的直径

543. 二叉树的直径

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

示例 :

给定二叉树

/ \

4 5

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

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

PS：

二叉树的直径不一定过根节点，因此需要去搜一遍所有子树(例如以root，root.left, root.right…为根节点的树)对应的直径，取最大值。

root的直径 = root左子树高度 + root右子树高度

root的高度 = max {root左子树高度, root右子树高度} + 1

/**

 * Definition for a binary tree node.

 * public class TreeNode {

 *     int val;

 *     TreeNode left;

 *     TreeNode right;

 *     TreeNode(int x) { val = x; }

 * }

 */

class Solution {

     private int max = 0;

    public int diameterOfBinaryTree(TreeNode root) {

        dfs(root);

        return max;

    }

    private int dfs(TreeNode root) {

        if (root == null) {

            return 0;

        }

        int leftHeight = dfs(root.left), rightHeight = dfs(root.right);

        max = Math.max(leftHeight + rightHeight, max);

        return Math.max(leftHeight, rightHeight) + 1;

    }

}

巴特西

Java实现 LeetCode 543 二叉树的直径

543. 二叉树的直径

最新文章

热门文章