2022/07/25

Leetcode Note: Go - Diameter of Binary Tree

Diameter of Binary Tree - LeetCode
https://leetcode.com/problems/diameter-of-binary-tree/

Go 言語で取り組んだメモ

所感

binary tree に存在する node を走査して diameter の長さを int で return ぅる
diameter は直径、今回の場合は最も離れている 2つの node の距離

回答

[Golang] Using closure to do postorder traverse. Time: O(N) - LeetCode Discuss
https://leetcode.com/problems/diameter-of-binary-tree/discuss/1381102/Golang-Using-closure-to-do-postorder-traverse.-Time%3A-O(N)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func diameterOfBinaryTree(root *TreeNode) int {
    //post order traverse
    // for each recursion we want to get what is the largest number of nodes single sided
    res := 0
    var postorder func(*TreeNode) int
    postorder = func(node *TreeNode) int {
        if node == nil {
            return 0
        }
        left := postorder(node.Left)
        right := postorder(node.Right)
        if left + right > res {
            res = left + right
        }
        if left > right {
            return left+1
        } else {
            return right+1
        }
    }
    postorder(root)
    return res
}

再帰で node を走査していき 2つの Node の距離を最高記録を記録していく