543_diameter_of_binary_tree

543. 二叉树的直径 简单

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

          1
         / \
        2   3
       / \     
      4   5    

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

代码参考：

package main

import "fmt"

func main() {
    root := &TreeNode{Val: 1}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 3}
    fmt.Println(diameterOfBinaryTree(root))
}

// 显然是找左子树最大路径与右子树最长路径
func diameterOfBinaryTree(root *TreeNode) int {
    var d int
    traverse(root, &d)
    return d
}

// 递归解法比较辣鸡
func traverse(root *TreeNode, maxD *int) {
    if root == nil {
        return
    }
    curD := depth(root.Left) + depth(root.Right)
    if curD > *maxD {
        *maxD = curD
    }

    traverse(root.Left, maxD)
    traverse(root.Right, maxD)
}

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

    lDepth := depth(root.Left) + 1
    rDepth := depth(root.Right) + 1
    if lDepth > rDepth {
        return lDepth
    }
    return rDepth
}