algorithms/leetcode/965-UnivaluedBinaryTree.go at master · freewu/algorithms · GitHub

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
package main

// 965. Univalued Binary Tree
// A binary tree is uni-valued if every node in the tree has the same value.
// Given the root of a binary tree, return true if the given tree is uni-valued, or false otherwise.

// Example 1:
//        1
//       /  \
//      1    1
//     /  \   \
//    1    1   1
// <img src="https://assets.leetcode.com/uploads/2018/12/28/unival_bst_1.png" />
// Input: root = [1,1,1,1,1,null,1]
// Output: true

// Example 2:
//        2
//       /  \
//      2    2
//     /  \
//    5    2
// <img src="https://assets.leetcode.com/uploads/2018/12/28/unival_bst_2.png" />
// Input: root = [2,2,2,5,2]
// Output: false

// Constraints:
//     The number of nodes in the tree is in the range [1, 100].
//     0 <= Node.val < 100

import "fmt"

// Definition for a binary tree node.
type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
// bfs
func isUnivalTree(root *TreeNode) bool {
    path := []*TreeNode{root}
    s := root.Val
    for i,j := 0,0 ; i<len(path) ; i = j {
        h := len(path)
        for ;j < h; j++ {
            if path[j].Val != s { return false }
            if path[j].Left != nil {
                if path[j].Left.Val != s { return false }
                path = append(path, path[j].Left)
            }
            if path[j].Right != nil {
                if path[j].Right.Val != s { return false }
                path = append(path, path[j].Right)
            }
        }
    }
    return true
}

// dfs
func isUnivalTree1(root *TreeNode) bool {
    if root == nil {
        return true
    }
    var dfs func(node *TreeNode, val int) bool
    dfs = func(node *TreeNode, val int) bool {
        if node == nil {
            return true
        } else if node.Val != val {
            return false
        }
        if node.Left != nil && !dfs(node.Left, val) {
            return false
        }
        if node.Right != nil && !dfs(node.Right, val) {
            return false
        }
        return true
    }
    if root.Left != nil && !dfs(root.Left, root.Val) {
        return false
    }
    if root.Right != nil && !dfs(root.Right, root.Val) {
        return false
    }
    return true
}

func main() {
    // Example 1:
    //        1
    //       /  \
    //      1    1
    //     /  \   \
    //    1    1   1
    // <img src="https://assets.leetcode.com/uploads/2018/12/28/unival_bst_1.png" />
    // Input: root = [1,1,1,1,1,null,1]
    // Output: true
    tree1 := &TreeNode {
        1,
        &TreeNode{
            1,
            &TreeNode{1, nil, nil},
            &TreeNode{1, nil, nil},
        },
        &TreeNode{1, nil, &TreeNode{1, nil, nil}, },
    }
    fmt.Println(isUnivalTree(tree1)) // true
    // Example 2:
    //        2
    //       /  \
    //      2    2
    //     /  \
    //    5    2
    // <img src="https://assets.leetcode.com/uploads/2018/12/28/unival_bst_2.png" />
    // Input: root = [2,2,2,5,2]
    // Output: false
    tree2 := &TreeNode {
        2,
        &TreeNode{
            2,
            &TreeNode{5, nil, nil },
            &TreeNode{2, nil, nil },
        },
        &TreeNode{2, nil, nil },
    }
    fmt.Println(isUnivalTree(tree2)) // true

    fmt.Println(isUnivalTree1(tree1)) // true
    fmt.Println(isUnivalTree1(tree2)) // true
}