【重点】【DFS】543.二叉树的直径

题目

法1：DFS两遍

不太好的方法

class Solution {

    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = diameterOfBinaryTree(root.left);
        int right = diameterOfBinaryTree(root.right);
        int cur = oneSideDepth(root.left) + oneSideDepth(root.right);

        return Math.max(cur, Math.max(left, right));
    }

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

法2：最佳DFS

设置全局变量！简化DFS!

class Solution {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        maxDepth(root);
        return res;
    }

    public int maxDepth(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = maxDepth(node.left);
        int right = maxDepth(node.right);
        res = res >= left + right ? res : left + right;
        return 1 + Math.max(left, right);
    }
}