543.二叉树的直径

题目描述

题解

DFS

方法一(时间复杂度不好)

对二叉树分析可得, 这道题要用到二叉树的最大深度.

在先序遍历的顺序下, 计算每个节点的左右子树最大深度, 然后记录下来, 不断更新最大的左右子树最大深度和.

public class lc543 {
    int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return diameter;
    }

    private void dfs(TreeNode root) {
        if (root != null) {
            dfs(root.left);
            dfs(root.right);
            diameter = Math.max(diameter, depth(root.left) + depth(root.right));
        }
    }

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

方法三(推荐)

方法一中每遍历到一个节点都要重新计算一下子树的深度, 改进的方向为在遍历的过程中计算左右子树的深度, 并通过递归过程传递该值.

class Solution {
    int diameter = 0;

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

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

}