2022/04/22

Leetcode Note: Go - Balanced Binary Tree

Binary Tree Inorder Traversal - LeetCode
https://leetcode.com/problems/binary-tree-inorder-traversal/

  • Go 言語で取り組んだメモ

所感

  • aaa

実装準備

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {
    
}

回答

32ms Golang solution with O(n) time and O(n) stack place - LeetCode Discuss
https://leetcode.com/problems/balanced-binary-tree/discuss/35843/32ms-Golang-solution-with-O(n)-time-and-O(n)-stack-place

func isBalanced(root *TreeNode) bool {
	return getDepth(root) >= 0
}

func getDepth(n *TreeNode) int {
	if n == nil {
		return 0
	}
	leftDepth, rightDepth := getDepth(n.Left), getDepth(n.Right)
	if leftDepth < 0 || rightDepth < 0 || leftDepth-rightDepth < -1 || leftDepth-rightDepth > 1 {
		return -1
	}
	if leftDepth > rightDepth {
		return leftDepth + 1
	}
	return rightDepth + 1
}
  • getDepth を実装して return された数値が 0 以上なら true と判定
  • getDepth では Left, Right を再帰的に調査
    • 各 Depth が 0 未満、 leftDepth - rightDepth が -1 未満、 leftDepth - rightDepth が 1 以上といった条件に合致したら -1 を return
    • leftDepth が rightDepth より大きければ leftDepth + 1 を return
    • それ以外なら rightDepth + 1 を return

See Also