[Golang][Leetcode][BinaryTree]刷題系列-110-Balanced Binary Tree

Steven included in Leetcode Golang

2021-09-01 306 words 2 minutes

/leetcode110_binarytree/golang_leetcode.png

Contents

110. Balanced Binary Tree

Level : Easy

原題連結 : Click

題目 :

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as:

a binary tree in which the left and right subtrees of every node differ in height by no more than 1.

Example :

Note

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: true

Example 2:

Input: root = [1,2,2,3,3,null,null,4,4] Output: false

Example 3:

Input: root = [] Output: true

解題思路 :

這題雖然難度為easy但其實還是需要細細思考才能掌握裡面的邏輯!
首先先了解題目的問題，題目需要我們找判斷該 binary tree 是否為 balanced tree
題目給balanced tree的定義是一個binary tree他的 left and right subtree的height之間不能差超過1，然後每一個subtree都是balanced tree
我們可以先就單一方面去想，先定義如何找到the height of tree的function，在這個function中，我們勢必要比較該tree的left subtree 與 right subtree 的 height誰比較大，這有點 dynamic programming的感覺，每一個最小單位的最佳解組合起來就是該問題的最佳解，這邊也一樣，每一個最小單位的max height subtree組起來就是max height subtree，這個觀念可以從 height , maxHeight function中觀察到
之後比subtree之間height的差值，若大於1，就可以直接結束程式，return false，反之則繼續做下去，對每一個node(每一個subtree)都做isBalanced function

Recursive解法

time complexity: O(n) , space complexity: O(1)

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {
    
    if root == nil {
        return true
    }
    
    lh, rh := height(root.Left), height(root.Right)
    
    if diff(lh, rh) > 1 {
        return false
    }
    
    return isBalanced(root.Left) && isBalanced(root.Right)
    
}

func diff(h1, h2 int) int{
    
    if h1 >= h2 {
        return h1 - h2
    }else{
        return h2 - h1
    }
}


func height(node *TreeNode) int {
    
    if node == nil {
        return 0
    }
    
    return 1 + maxHeight(height(node.Left), height(node.Right))
    
}

func maxHeight(h1, h2 int) int{
    
    if h1 >= h2 {
        return h1
    }else {
        return h2
    }
    
}

最後祝福努力認真的各位 “All your dream of are hidden in your daily life” 我們峰頂見!!!