本文共 2067 字，大约阅读时间需要 6 分钟。

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:

1         / \        2   3       / \           4   5

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

我的想法

bfs遍历每一个结点，对于每一个结点，dfs其左右结点并相加

class Solution {
       int res;    public int diameterOfBinaryTree(TreeNode root) {
           if(root == null) {
               return 0;        }        res = 0;        helper(root);        return res;    }    private void helper(TreeNode root) {
           Stack
   
     stack = new Stack<>();        stack.push(root);        while(!stack.isEmpty()) {
               int size = stack.size();            for(int i = 0; i < size; i++) {
                   TreeNode node = stack.pop();                int sum = dfs(node.left) + dfs(node.right);                res = Math.max(res, sum);                if(node.left != null) {
                       stack.push(node.left);                }                if(node.right != null) {
                       stack.push(node.right);                }            }        }    }    private int dfs(TreeNode root) {
           if(root == null) {
               return 0;        }        int left = dfs(root.left);        int right = dfs(root.right);        return Math.max(left, right) + 1;    }}
   

DFS已经自底向上遍历所有结点了，再来一圈BFS其实很没必要。利用res记录全局最大，返回全局最大即可

class Solution {
       int res;    public int diameterOfBinaryTree(TreeNode root) {
           res = 0;        if(root == null) {
               return res;        }        dfs(root);        return res;    }    private int dfs(TreeNode root) {
           if(root == null) {
               return 0;        }        int left = dfs(root.left);        int right = dfs(root.right);        res = Math.max(res, left + right);        return Math.max(left, right) + 1;    }}

解答

转载地址：http://vyqvb.baihongyu.com/