l543 diameter of binary tree

题目描述

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:
Given a binary tree

1
2
3
4
5

    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.

解题思路

Go实现

Go递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func (root *TreeNode) int {
    if root == nil {
        return 0
    }

    d := 0
    height(root, &d)
    return d
}

func height(root *TreeNode, d *int) int  {
    if root == nil{
        return  0
    }

    hLeft := height(root.Left, d)
    hRight := height(root.Right, d)
    if *d<hLeft+hRight {
        *d = hLeft + hRight
    }
    if hLeft>hRight {
        return hLeft+1
    }else{
        return hRight+1
    }
}