二叉树的直径——lintcode1181(Diameter of binary tree — lintcode1181)

二叉树的直径

题目:二叉树的直径

给定一颗二叉树,您需要计算树的直径长度。 二叉树的直径是树中任意两个节点之间最长路径的长度。

给定一棵二叉树 
          1
         / \
        2   3
       / \     
      4   5    
返回3, 这是路径[4,2,1,3] 或者 [5,2,1,3]的长度.

示例:

输入:[2,3,#,1]
输出:2

解释:
      2
    /
   3
 /
1

题解:递归

public class Solution {
    private int maxValue;

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

Diameter of binary tree

Title: diameter of binary tree

Given a binary tree, you need to calculate the diameter and length of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in the tree.

给定一棵二叉树 
          1
         / \
        2   3
       / \     
      4   5    
返回3, 这是路径[4,2,1,3] 或者 [5,2,1,3]的长度.

< strong > example: < / strong >

输入:[2,3,#,1]
输出:2

解释:
      2
    /
   3
 /
1

Problem solution: recursion

public class Solution {
    private int maxValue;

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