Leetcode-tree

LeetCode 编程训练的积累,目前在努力做题中,日后整理!

<!– more –>

1 binary tree traversal

1.1 level order

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
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}

lo_arr := [][]int{
[]int{root.Val},
}

llo_arr := levelOrder(root.Left)
rlo_arr := levelOrder(root.Right)

if len(llo_arr) > 0 || len(rlo_arr) > 0 {
var index int
for {
if index < len(llo_arr) && index < len(rlo_arr) {
lo_arr = append(lo_arr, append(llo_arr[index], rlo_arr[index]...))
} else {
break
}
index += 1
}

if len(llo_arr) > index {
lo_arr = append(lo_arr, llo_arr[index:]...)
}

if len(rlo_arr) > index {
lo_arr = append(lo_arr, rlo_arr[index:]...)
}
}

return lo_arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(levelOrder(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(levelOrder(root))
}

1.2 level order bottom

1
2
3
4
5
6
7
8
9
10
<<bt-level-order>>
func levelOrderBottom(root *TreeNode) [][]int {
lo_arr := levelOrder(root)
lob_arr := make([][]int, 0)
for index, _ := range lo_arr {
lob_arr = append([][]int{lo_arr[index]}, lob_arr...)
}

return lob_arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(levelOrderBottom(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(levelOrderBottom(root))
}

1.3 zigzag level order

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
  <<bt-level-order>>
func zigzagLevelOrder(root *TreeNode) [][]int {
lo_arr := levelOrder(root)
zlo_arr := make([][]int, 0)
for index, _ := range lo_arr {
lo := lo_arr[index]
if index % 2 == 1 {
zlo := make([]int, 0)
for index, _ := range lo {
zlo = append([]int{lo[index]}, zlo...)
}
zlo_arr = append(zlo_arr, zlo)
} else {
zlo_arr = append(zlo_arr, lo)
}
}

return zlo_arr
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(zigzagLevelOrder(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(zigzagLevelOrder(root))
}

1.4 inOrder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}

return append(
append(inorderTraversal(root.Left), root.Val),
inorderTraversal(root.Right)...)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(inorderTraversal(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(inorderTraversal(root))
}

1.5 preOrder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func preorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}

return append(
append([]int{root.Val}, preorderTraversal(root.Left)...),
preorderTraversal(root.Right)...)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(preorderTraversal(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(preorderTraversal(root))
}

1.6 postOrder

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func postorderTraversal(root *TreeNode) []int {
if root == nil {
return []int{}
}

return append(
append(postorderTraversal(root.Left), postorderTraversal(root.Right)...),
root.Val)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(postorderTraversal(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(postorderTraversal(root))
}

2 binary tree

1
2
3
4
5
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
1
2
3
4
5
struct TreeLinkNode {
int val;
TreeLinkNode *left, *right, *next;
TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};
1
2
3
4
5
6
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

2.1 max depth

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}

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

return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(maxDepth(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(maxDepth(root))
}

2.2 paths

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
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func binaryTreePaths(root *TreeNode) []string {
if root == nil {
return []string{}
}

str := fmt.Sprintf("%d", root.Val)
if root.Left == nil && root.Right == nil {
return []string{str}
}

paths := append(
binaryTreePaths(root.Left),
binaryTreePaths(root.Right)...,
)
for index, path := range paths {
paths[index] = str + "->" + path
}

return paths
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(binaryTreePaths(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(binaryTreePaths(root))
}

2.3 isBalanced

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<<bt-max-depth>>
func isBalanced(root *TreeNode) bool {
if root == nil {
return true
}

ldepth := maxDepth(root.Left)
rdepth := maxDepth(root.Right)
ddepth := ldepth - rdepth
if ddepth > 1 || ddepth < -1 {
return false
}

return isBalanced(root.Left) && isBalanced(root.Right)
}
1
2
3
4
5
6
7
8
9
10
11
12
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
}

fmt.Println(isBalanced(root))
root.Left.Left = &TreeNode{Val:4}
fmt.Println(isBalanced(root))
}

2.4 invert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}

root.Left, root.Right = invertTree(root.Right), invertTree(root.Left)
return root
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(invertTree(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(invertTree(root))
}

2.5 tilt

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
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

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

return root.Val + sumTree(root.Left) + sumTree(root.Right)
}

func abs(num int) int {
if num < 0 {
return -num
} else {
return num
}
}

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

return abs(sumTree(root.Left)-sumTree(root.Right)) +
findTilt(root.Left) + findTilt(root.Right)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(findTilt(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(findTilt(root))
}

2.6 construct string

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func tree2str(t *TreeNode) string {
if t == nil {
return ""
}

str := fmt.Sprintf("%d", t.Val)
if t.Left == nil && t.Right == nil {
return str
}

if t.Left != nil {
str += fmt.Sprintf("(%s)", tree2str(t.Left))
} else {
str += "()"
}

if t.Right != nil {
str += fmt.Sprintf("(%s)", tree2str(t.Right))
}

return str
}

2.7 symmetric

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
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}

return isMirror(root.Left, root.Right)
}

func isMirror(lr *TreeNode, rr *TreeNode) bool {
if lr == nil && rr == nil {
return true
}

if lr == nil || rr == nil {
return false
}

if lr.Val != rr.Val {
return false
}

return isMirror(lr.Left, rr.Right) && isMirror(lr.Right, rr.Left)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 2,
},
}

fmt.Println(isSymmetric(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(isSymmetric(root))
}

2.8 subtree

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
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func isSubtree(s *TreeNode, t *TreeNode) bool {
if t == nil {
return true
}

if s == nil {
return false
}

if s.Val == t.Val {
return isSame(s, t) || isSubtree(s.Left, t) || isSubtree(s.Right, t)
} else {
return isSubtree(s.Left, t) || isSubtree(s.Right, t)

}
}

func isSame(s *TreeNode, t *TreeNode) bool {
if s == nil && t == nil {
return true
}

if s == nil || t == nil {
return false
}

if s.Val != t.Val {
return false
}

return isSame(s.Left, t.Left) && isSame(s.Right, t.Right)
}
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
func main() {
s := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 4,
Left: &TreeNode{
Val: 1,
},
Right: &TreeNode{
Val: 2,
},
},
Right: &TreeNode{
Val: 5,
},
}

t := &TreeNode{
Val: 4,
Left: &TreeNode{
Val: 1,
},
Right: &TreeNode{
Val: 2,
},
}

fmt.Println(isSubtree(s, t))
s.Left.Right = &TreeNode{
Val: 0,
}
fmt.Println(isSubtree(s, t))
}

2.9 diameter

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
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

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

if root.Left == nil && root.Right == nil {
return 0
}

if root.Right == nil {
return max(1+maxSide(root.Left), diameterOfBinaryTree(root.Left))
}

if root.Left == nil {
return max(1+maxSide(root.Right), diameterOfBinaryTree(root.Right))
}

return max(
max(
(2+maxSide(root.Left)+maxSide(root.Right)),
diameterOfBinaryTree(root.Left),
), diameterOfBinaryTree(root.Right))
}

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

if root.Left == nil && root.Right == nil {
return 0
}

return 1 + max(maxSide(root.Left), maxSide(root.Right))
}

func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}
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
func main() {
s := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 4,
Left: &TreeNode{
Val: 1,
},
Right: &TreeNode{
Val: 2,
},
},
Right: &TreeNode{
Val: 5,
},
}

t := &TreeNode{
Val: 4,
Left: &TreeNode{
Val: 1,
},
Right: &TreeNode{
Val: 2,
},
}

fmt.Println(diameterOfBinaryTree(s))
fmt.Println(diameterOfBinaryTree(t))
}

2.10 count complete tree nodes

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
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
int countNodes(TreeNode* root) {
if (root == NULL) {
return 0;
}

int ldepth = this->getLeftDepth(root);
int rdepth = this->getRightDepth(root);
if (ldepth == rdepth) {
return this->pow(2,ldepth) -1;
}

return countNodes(root->left) + countNodes(root->right)+1;
}

int getLeftDepth(TreeNode *root) {
if (root == NULL) {
return 0;
}

return 1+getLeftDepth(root->left);
}

int getRightDepth(TreeNode *root) {
if (root == NULL) {
return 0;
}

return 1+getRightDepth(root->right);
}

int pow(int base, int exp) {
int p=1;
while (exp>0) {
p = p*base;
exp = exp- 1;
}

return p;
}
};
1
2
3
4
5
6
7
8
int main() {
TreeNode* p = new TreeNode(5);
p->left = new TreeNode(3);
p->right = new TreeNode(7);

Solution s;
std::cout << s.countNodes(p);
}

2.11 implement trie

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
type Trie struct {
is_end int
next map[byte]*Trie
}

/** Initialize your data structure here. */
func Constructor() Trie {
var trie Trie
trie.next = make(map[byte]*Trie)
return trie
}

/** Inserts a word into the trie. */
func (this *Trie) Insert(word string) {
byte_arr := []byte(word)
this.insert(byte_arr)
}

func (this *Trie) insert(byte_arr []byte) {
if len(byte_arr) < 1 {
return
}

if next_trie, ok := this.next[byte_arr[0]]; ok {
if len(byte_arr) > 1 {
next_trie.insert(byte_arr[1:])
} else {
next_trie.is_end = 1
}
} else {
trie := Constructor()
next_trie := &trie
this.next[byte_arr[0]] = next_trie
if len(byte_arr) > 1 {
next_trie.insert(byte_arr[1:])
} else {
next_trie.is_end = 1
}
}
}

/** Returns if the word is in the trie. */
func (this *Trie) Search(word string) bool {
byte_arr := []byte(word)
return this.search(byte_arr)
}

func (this *Trie) search(byte_arr []byte) bool {
if len(byte_arr) < 1 {
if len(this.next) == 0 {
return true
} else {
return false
}
}

if next_trie, ok := this.next[byte_arr[0]]; ok {
if len(byte_arr) == 1 && next_trie.is_end == 1 {
return true
} else {
return next_trie.search(byte_arr[1:])
}
} else {
return false
}
}

/** Returns if there is any word in the trie that starts with the given prefix. */
func (this *Trie) StartsWith(prefix string) bool {
byte_arr := []byte(prefix)
return this.startsWith(byte_arr)
}

func (this *Trie) startsWith(byte_arr []byte) bool {
if len(byte_arr) < 1 {
return true
}

if next_trie, ok := this.next[byte_arr[0]]; ok {
return next_trie.startsWith(byte_arr[1:])
} else {
return false
}
}

/**
* Your Trie object will be instantiated and called as such:
* obj := Constructor();
* obj.Insert(word);
* param_2 := obj.Search(word);
* param_3 := obj.StartsWith(prefix);
*/

1
2
3
4
5
6
func main() {
trie := Constructor()
trie.Insert("hello")
fmt.Println(trie.Search("hello"))
fmt.Println(trie.StartsWith("hello"))
}

2.12 merge two binary tree

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
func mergeTrees(t1 *TreeNode, t2 *TreeNode) *TreeNode {
if t1 == nil && t2 == nil {
return nil
}

if t2 == nil {
return &TreeNode{
Val: t1.Val,
Left: mergeTrees(t1.Left, nil),
Right: mergeTrees(t1.Right, nil),
}
}

if t1 == nil {
return &TreeNode{
Val: t2.Val,
Left: mergeTrees(nil, t2.Left),
Right: mergeTrees(nil, t2.Right),
}
}

return &TreeNode{
Val: t1.Val + t2.Val,
Left: mergeTrees(t1.Left, t2.Left),
Right: mergeTrees(t1.Right, t2.Right),
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
func main() {
t1 := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 3},
}

t2 := &TreeNode{
Val: 2,
Right: &TreeNode{Val: 3},
}

fmt.Println(tree2str(mergeTrees(t1, t2)))
}

2.13 flatten bt to linked list

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
func flatten(root *TreeNode) {
if root == nil {
return
}

flatten(root.Left)
flatten(root.Right)

if root.Left == nil {
return
}

lr_r := root.Left
for {
if lr_r.Right == nil {
break
}
lr_r = lr_r.Right
}
lr_r.Right = root.Right

root.Right = root.Left
root.Left = nil

return
}
1
2
3
4
5
6
7
8
9
func main() {
t := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 3},
Right: &TreeNode{Val: 5},
}

fmt.Println(tree2str(flatten(t)))
}

2.14 sum of left leaves

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func sumOfLeftLeaves(root *TreeNode) int {
if root == nil {
return 0
}

if root.Left == nil && root.Right == nil {
return 0
}

if root.Left != nil {
if isLeave(root.Left) {
return root.Left.Val + sumOfLeftLeaves(root.Right)
} else {
return sumOfLeftLeaves(root.Left) + sumOfLeftLeaves(root.Right)
}
} else {
return sumOfLeftLeaves(root.Right)
}
}

func isLeave(node *TreeNode) bool {
return node.Left == nil && node.Right == nil
}
1
2
3
4
5
6
7
8
9
10
11
12
13
func main() {
t := &TreeNode{
Val: 3,
Left: &TreeNode{Val: 9},
Right: &TreeNode{
Val: 20,
Left: &TreeNode{Val: 15},
Right: &TreeNode{Val: 7},
},
}

fmt.Println(sumOfLeftLeaves(t))
}

2.15 find bottom left tree value

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
func findBottomLeftValue(root *TreeNode) int {
if root == nil {
return 0
}

lnode_arr := []*TreeNode{root}
for {
n_lnode_arr := make([]*TreeNode, 0)
for index, _ := range lnode_arr {
node := lnode_arr[index]
if node.Left != nil {
n_lnode_arr = append(n_lnode_arr, node.Left)
}
if node.Right != nil {
n_lnode_arr = append(n_lnode_arr, node.Right)
}
}

if len(n_lnode_arr) > 0 {
lnode_arr = n_lnode_arr
} else {
break
}
}

return lnode_arr[0].Val
}
1
2
3
4
5
6
7
8
9
10
11
12
func main() {
t := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 3},
Right: &TreeNode{
Val: 5,
Left: &TreeNode{Val: 10},
},
}

fmt.Println(findBottomLeftValue(t))
}

2.16 right side view

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
func rightSideView(root *TreeNode) []int {
if root == nil {
return []int{}
}

lnode_arr := []*TreeNode{root}
rsv_arr := []int{root.Val}
for {
n_lnode_arr := make([]*TreeNode, 0)
for index, _ := range lnode_arr {
node := lnode_arr[index]
if node.Left != nil {
n_lnode_arr = append(n_lnode_arr, node.Left)
}
if node.Right != nil {
n_lnode_arr = append(n_lnode_arr, node.Right)
}
}

if len(n_lnode_arr) > 0 {
rsv_arr = append(rsv_arr, n_lnode_arr[len(n_lnode_arr)-1].Val)
lnode_arr = n_lnode_arr
} else {
break
}
}

return rsv_arr
}
1
2
3
4
5
6
7
8
9
func main() {
t := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 3},
Right: &TreeNode{Val: 5},
}

fmt.Println(rightSideView(t))
}

2.17 find largest value in each tree row

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
func largestValues(root *TreeNode) []int {
if root == nil {
return []int{}
}

lnode_arr := []*TreeNode{root}
rmax_arr := []int{root.Val}
for {
n_lnode_arr := make([]*TreeNode, 0)
for index, _ := range lnode_arr {
node := lnode_arr[index]
if node.Left != nil {
n_lnode_arr = append(n_lnode_arr, node.Left)
}
if node.Right != nil {
n_lnode_arr = append(n_lnode_arr, node.Right)
}
}

if len(n_lnode_arr) > 0 {
rmax_val := n_lnode_arr[0].Val
for index, _ := range n_lnode_arr {
node := n_lnode_arr[index]
if node.Val > rmax_val {
rmax_val = node.Val
}
}
lnode_arr = n_lnode_arr
rmax_arr = append(rmax_arr, rmax_val)
} else {
break
}
}

return rmax_arr
}
1
2
3
4
5
6
7
8
9
func main() {
t := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 3},
Right: &TreeNode{Val: 5},
}

fmt.Println(largestValues(t))
}

2.18 most frequent subtree sum

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
func findFrequentTreeSum(root *TreeNode) []int {
if root == nil {
return []int{}
}

sum_M := make(map[int]int)
collectTreeSum(root, sum_M)
var max_count int
for _, count := range sum_M {
if count > max_count {
max_count = count
}
}

ft_sum_arr := make([]int, 0)
for sum, count := range sum_M {
if count == max_count {
ft_sum_arr = append(ft_sum_arr, sum)
}
}

return ft_sum_arr
}

func collectTreeSum(root *TreeNode, sum_M map[int]int) int {
if root == nil {
return 0
}

sum := collectTreeSum(root.Left, sum_M) + root.Val + collectTreeSum(root.Right, sum_M)
sum_M[sum] = sum_M[sum] + 1
return sum
}
1
2
3
4
5
6
7
8
9
func main() {
t := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 3},
Right: &TreeNode{Val: 5},
}

fmt.Println(findFrequentTreeSum(t))
}

2.19 construct binary tree from preorder and inorder traversal

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
func buildTree(preorder []int, inorder []int) *TreeNode {
if len(preorder) == 0 {
return nil
}

if len(preorder) == 1 {
return &TreeNode{
Val: preorder[0],
}
}

rio_index := find(inorder, preorder[0])
return &TreeNode{
Val: preorder[0],
Left: buildTree(preorder[1:rio_index+1], inorder[0:rio_index]),
Right: buildTree(preorder[rio_index+1:], inorder[rio_index+1:]),
}
}

func find(a []int, x int) int {
for index, _ := range a {
if a[index] == x {
return index
}
}

return -1
}
1
2
3
4
func main() {
fmt.Println(tree2str(buildTree([]int{1,2,3}, []int{2,1,3})))
fmt.Println(tree2str(buildTree([]int{1,2,4,3,5}, []int{4,2,1,3,5})))
}

2.20 construct binary tree from inorder and postorder traversal

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
func buildTree(inorder []int, postorder []int) *TreeNode {
if len(inorder) == 0 {
return nil
}

if len(inorder) == 1 {
return &TreeNode{Val: inorder[0]}
}

rio_index := find(inorder, postorder[len(postorder)-1])
return &TreeNode{
Val: postorder[len(postorder)-1],
Left: buildTree(inorder[0:rio_index], postorder[0:rio_index]),
Right: buildTree(inorder[rio_index+1:], postorder[rio_index:(len(postorder)-1)]),
}
}

func find(a []int, x int) int {
for index, _ := range a {
if a[index] == x {
return index
}
}

return -1
}
1
2
3
4
func main() {
fmt.Println(tree2str(buildTree([]int{2,1,3}, []int{2,3,1})))
fmt.Println(tree2str(buildTree([]int{4,2,1,3,5}, []int{4,2,5,3,1})))
}

2.21 populating next right pointers in each node

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
struct TreeLinkNode {
int val;
TreeLinkNode *left, *right, *next;
TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};

struct ConnectObj {
TreeLinkNode *left_most;
TreeLinkNode *right_most;
ConnectObj() : left_most(NULL), right_most(NULL) {}
};

std::deque<ConnectObj>
mergeConnect(
std::deque<ConnectObj> lc_dq,
std::deque<ConnectObj> rc_dq)
{
for (std::deque<ConnectObj>::iterator it = lc_dq.begin(); it != lc_dq.end(); ++it) {
if (it->right_most == NULL) {
it->right_most = it->left_most;
}
}

for (std::deque<ConnectObj>::iterator it = rc_dq.begin(); it != rc_dq.end(); ++it) {
if (it->left_most == NULL) {
it->left_most = it->right_most;
}
}

int min_size = lc_dq.size() < rc_dq.size() ? lc_dq.size() : rc_dq.size();
for (int index=0; index < min_size; index+=1) {
if (lc_dq[index].right_most != NULL && rc_dq[index].left_most != NULL){
lc_dq[index].right_most->next = rc_dq[index].left_most;
}

lc_dq[index].right_most = rc_dq[index].right_most;
rc_dq[index].left_most = lc_dq[index].left_most;
}

return lc_dq.size() > rc_dq.size() ? lc_dq : rc_dq;
}

class Solution {
public:
void connect(TreeLinkNode *root) {
if (root == NULL) {
return;
}

this->connectHelper(root);
return;
}

std::deque<ConnectObj> connectHelper(TreeLinkNode *root) {
std::deque<ConnectObj> conn_dq;
if (root == NULL) {
return conn_dq;
}

ConnectObj rc_node;
rc_node.left_most = root;
rc_node.right_most = root;
if ((root->left == NULL) && (root->right == NULL)) {
conn_dq.push_back(rc_node);
return conn_dq;
}

std::deque<ConnectObj> lc_dq = connectHelper(root->left);
std::deque<ConnectObj> rc_dq = connectHelper(root->right);
std::deque<ConnectObj> merge_dq = mergeConnect(lc_dq, rc_dq);
merge_dq.push_front(rc_node);
return merge_dq;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main() {
TreeLinkNode* p = new TreeLinkNode(5);
p->left = new TreeLinkNode(3);
p->left->left = new TreeLinkNode(1);
p->left->left->left = new TreeLinkNode(1);
p->left->right = new TreeLinkNode(2);
p->right = new TreeLinkNode(7);
p->right->right = new TreeLinkNode(9);

Solution s;
s.connect(p);
TreeLinkNode *left = p;
while (left != NULL) {
TreeLinkNode *head = left;
while (head !=NULL){
std::cout << head->val << " ";
head = head->next;
}
std::cout << "\n";
left = left->left;
}
return 0;
}

2.22 add one row to tree

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
func addOneRow(root *TreeNode, v int, d int) *TreeNode {
if d == 1 {
return &TreeNode{
Val: v,
Left: root,
}
}

if root == nil || d < 2 {
return nil
}

addOneRowHelper(root, v, d)
return root
}

func addOneRowHelper(root *TreeNode, v int, d int) {
if root == nil {
return
}

if d == 2 {
root.Left = &TreeNode{
Val: v,
Left: root.Left,
}
root.Right = &TreeNode{
Val: v,
Right: root.Right,
}
return
}

addOneRowHelper(root.Left, v, d-1)
addOneRowHelper(root.Right, v, d-1)
return
}
1
2
3
4
5
6
7
8
9
10
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 3},
Right: &TreeNode{Val: 4},
}

fmt.Println(tree2str(addOneRow(root, 2, 1)))
fmt.Println(tree2str(addOneRow(root, 2, 2)))
}

2.23 lowest common ancestor of a bt

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
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL || p == root || q == root) {
return root;
}

TreeNode *left = lowestCommonAncestor(root->left, p, q);
TreeNode *right = lowestCommonAncestor(root->right, p, q);

if (left != NULL && right != NULL) {
return root;
}

if (left != NULL) {
return left;
}

if (right != NULL) {
return right;
}

return NULL;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main() {
TreeNode* p = new TreeNode(5);
p->left = new TreeNode(3);
p->left->left = new TreeNode(1);
p->left->left->left = new TreeNode(0);
p->left->right = new TreeNode(2);
p->right = new TreeNode(7);
p->right->right = new TreeNode(9);

Solution s;
std::cout << s.lowestCommonAncestor(p, p->left->left, p->right->right)->val;
std::cout << s.lowestCommonAncestor(p, p->left->left, p->left->right)->val;
return 0;
}

2.24 serialize and deserialize bt

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
<<bt-node-def-cpp>>

int find_bracket_end(string str, int b_start) {
std::stack<char> b_stack;
int b_end=0;
for (int index = b_start; index < str.size(); index += 1) {
char c = str[index];
switch (c) {
case '(':
b_stack.push(c);
break;
case ')':
b_stack.pop();
break;
default:
break;
}
if (b_stack.empty()==true) {
b_end = index;
break;
}
}
return b_end;
}

string tree2str(TreeNode* t) {
if (t == NULL) {
return "";
}

ostringstream os;
os << t->val;
if (t->left == NULL && t->right == NULL) {
return os.str();
}

if (t->left != NULL) {
os << "(" << tree2str(t->left) << ")";
} else {
os << "()";
}

if (t->right != NULL) {
os << "(" << tree2str(t->right) << ")";
}

return os.str();
}

TreeNode* str2tree(string str) {
if (str == "" || str == "()") {
return NULL;
}

int b_start = str.find("(");
if (b_start < 0) {
int num = std::atoi(str.c_str());
return new TreeNode(num);
}

string num_str = str.substr(0, b_start);
int num = std::atoi(num_str.c_str());
TreeNode* root = new TreeNode(num);

int b_end = find_bracket_end(str, b_start);
if (b_end-b_start > 1) {
root->left = str2tree(str.substr(b_start+1, b_end));
}

b_start = b_end+1;
if (b_start < str.size() && str[b_start]=='('){
b_end = find_bracket_end(str, b_start);
if (b_end-b_start > 1) {
root->right = str2tree(str.substr(b_start+1, b_end));
}
}

return root;
}

class Codec {
public:
// Encodes a tree to a single string.
string serialize(TreeNode* root) {
return tree2str(root);
}

// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {
return str2tree(data);
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 using namespace std;


int main() {
TreeNode* p = new TreeNode(5);
p->left = new TreeNode(3);
p->left->left = new TreeNode(1);
p->left->left->left = new TreeNode(1);
p->left->right = new TreeNode(2);
p->right = new TreeNode(7);
p->right->right = new TreeNode(9);

Codec codec;
string encode_str =codec.serialize(p);
std::cout << encode_str << '\n';

TreeNode* np = codec.deserialize(encode_str);
encode_str = codec.serialize(np);
std::cout << encode_str << '\n';

return 0;
}

2.25 average of levels in binary tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func averageOfLevels(root *TreeNode) []float64 {
lo_arr := levelOrder(root)
aveOfLevels := make([]float64, 0)
for index, _ := range lo_arr {
lo := lo_arr[index]
var sum int
for _, val := range lo {
sum += val
}
ave := float64(sum) / float64(len(lo))
aveOfLevels = append(aveOfLevels, ave)
}

return aveOfLevels
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(averageOfLevels(root))
root.Left.Left = &TreeNode{Val:4}
root.Right.Right = &TreeNode{Val:5}
fmt.Println(averageOfLevels(root))
}

2.26 TODO house robber III

3 bst

3.1 BSTIterator

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
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

struct Node {
int val;
Node *next;
Node(int x) : val(x), next(NULL) {}
};

Node* convertBST2SortedLst(TreeNode *lct,TreeNode *pn, TreeNode *rct) {
Node *lhead = NULL;
if (lct != NULL) {
lhead = convertBST2SortedLst(lct->left, lct, lct->right);
}

Node *pln = new Node(pn->val);

Node *rhead = NULL;
if (rct != NULL){
rhead = convertBST2SortedLst(rct->left, rct, rct->right);
}

Node *head = NULL;
if (lhead != NULL) {
pln->next = rhead;
head = lhead;
while (lhead->next != NULL) {
lhead = lhead->next;
}
lhead->next = pln;
} else {
pln->next = rhead;
head = pln;
}
return head;
}

class BSTIterator {
Node* head;
public:
BSTIterator(TreeNode *root) {
if (root != NULL) {
head = convertBST2SortedLst(root->left, root, root->right);
} else {
head = NULL;
}
}

/** @return whether we have a next smallest number */
bool hasNext() {
if (this->head != NULL) {
return true;
} else {
return false;
}
}

/** @return the next smallest number */
int next() {
if (this->head== NULL) {
return 0;
}

Node *oldHead = head;
head = head->next;
int num = oldHead->val;
delete oldHead;
oldHead = NULL;
return num;
}

~BSTIterator(){
Node *oldHead = NULL;
while (head != NULL){
oldHead = head;
head = head->next;
delete oldHead;
oldHead = NULL;
}
}
};

/**
* Your BSTIterator will be called like this:
* BSTIterator i = BSTIterator(root);
* while (i.hasNext()) cout << i.next();
*/

1
2
3
4
5
6
7
8
9
10
int main() {
TreeNode* p = new TreeNode(5);
p->left = new TreeNode(3);
p->right = new TreeNode(7);

BSTIterator i = BSTIterator(p);
while (i.hasNext())
std::cout << i.next();
return 0;
}

3.2 to greater tree

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
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func convertBST(root *TreeNode) *TreeNode {
if root == nil {
return nil
}

return convertBSTHelper(root, 0)
}

func convertBSTHelper(root *TreeNode, upper int) *TreeNode {
if root == nil {
return nil
}

if root.Left == nil && root.Right == nil {
root.Val += upper
return root
}

if root.Right != nil {
minNode := findMinBST(root.Right)
root.Right = convertBSTHelper(root.Right, upper)
root.Val += minNode.Val
} else {
root.Val += upper
}

if root.Left != nil {
root.Left = convertBSTHelper(root.Left, root.Val)
}

return root
}

func findMinBST(root *TreeNode) *TreeNode {
if root == nil || root.Left == nil {
return root
}

return findMinBST(root.Left)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func main() {
root := &TreeNode{
Val: 0,
Left: &TreeNode{
Val: -1,
Left: &TreeNode{
Val: -3,
},
},
Right: &TreeNode{
Val: 2,
Right: &TreeNode{
Val: 4,
},
},
}

fmt.Println(convertBST(root))
fmt.Println(root.Left)
fmt.Println(root.Left.Left)
fmt.Println(root.Right.Right)
}

3.3 validate

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
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func isValidBST(root *TreeNode) bool {
if root == nil {
return true
}

return isValidLeftBST(root.Left, root.Val) && isValidRightBST(root.Right, root.Val)
}

func isValidLeftBST(root *TreeNode, upper int) bool {
if root == nil {
return true
}

if root.Val >= upper {
return false
}

return isValidLeftBST(root.Left, root.Val) && isValidSubBST(root.Right, root.Val, upper)
}

func isValidRightBST(root *TreeNode, lower int) bool {
if root == nil {
return true
}

if root.Val <= lower {
return false
}

return isValidRightBST(root.Right, root.Val) && isValidSubBST(root.Left, lower, root.Val)
}

func isValidSubBST(root *TreeNode, lower int, upper int) bool {
if root == nil {
return true
}

if root.Val >= upper || root.Val <= lower {
return false
}

return isValidSubBST(root.Left, lower, root.Val) && isValidSubBST(root.Right, root.Val, upper)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{
Val: 2,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(isValidBST(root))

root = &TreeNode{
Val: 2,
Left: &TreeNode{
Val: 1,
},
Right: &TreeNode{
Val: 3,
},
}
fmt.Println(isValidBST(root))
}

3.4 find mode

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
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func findMode(root *TreeNode) []int {
if root == nil {
return []int{}
}

modes := collect(root)
if len(modes) < 1 {
return modes
}

for i := 1; i < len(modes); i += 1 {
for j := i; j > 0; j -= 1 {
if modes[j] < modes[j-1] {
modes[j], modes[j-1] = modes[j-1], modes[j]
}
}
}

var max_count int
var count int
var pre int
n_modes := make([]int, 0)
for index, mode := range modes {
if index == 0 {
max_count = 1
pre = mode
count = 1
n_modes = append(n_modes, mode)
continue
}

if mode == pre {
count += 1
}

if mode != pre {
pre = mode
count = 1
}

if count == max_count {
n_modes = append(n_modes, mode)
}
if count > max_count {
max_count = count
n_modes = []int{mode}
}
}

return n_modes
}

func collect(root *TreeNode) []int {
if root == nil {
return []int{}
}

return append(append(collect(root.Left), root.Val), collect(root.Right)...)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func main() {
root := &TreeNode{
Val: 0,
Left: &TreeNode{
Val: -1,
Left: &TreeNode{
Val: -1,
},
},
Right: &TreeNode{
Val: 2,
Right: &TreeNode{
Val: 2,
},
},
}

fmt.Println(findMode(root))
}

3.5 convert sorted array to bst

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
func sortedArrayToBST(nums []int) *TreeNode {
if len(nums) == 0 {
return nil
}

if len(nums) == 1 {
return &TreeNode{
Val: nums[0],
}
}

if len(nums) == 2 {
return &TreeNode{
Val: nums[1],
Left: &TreeNode{
Val: nums[0],
},
}
}

mid := len(nums) / 2
return &TreeNode{
Val: nums[mid],
Left: sortedArrayToBST(nums[:mid]),
Right: sortedArrayToBST(nums[mid+1:]),
}
}
1
2
3
4
5
func main() {
fmt.Println(tree2str(sortedArrayToBST([]int{1,2,3})))
fmt.Println(tree2str(sortedArrayToBST([]int{1,2,3,4,5,6})))
fmt.Println(tree2str(sortedArrayToBST([]int{1,2,3,4,5,6,7,8})))
}

3.6 lowest common ancestor

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
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == NULL) {
return NULL;
}

if (p->val > q->val) {
TreeNode *tmp = p;
p=q;
q=tmp;
}

if (root->val>p->val && root->val<q->val) {
return root;
}

if (root->val < p->val) {
return lowestCommonAncestor(root->right, p, q);
}

if (root->val > q->val) {
return lowestCommonAncestor(root->left, p, q);
}

if (root->val == p->val) {
return root;
}

if (root->val == q->val) {
return root;
}

return NULL;
}
};
1
2
3
4
5
6
7
8
int main() {
TreeNode* p = new TreeNode(5);
p->left = new TreeNode(3);
p->right = new TreeNode(7);

Solution s;
std::cout << s.lowestCommonAncestor(p, p->left, p->right)->val;
}

3.7 recover binary search tree

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
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

type RecoverNode struct {
Pre *TreeNode
Ppre *TreeNode
Is_recover int
Illegal *TreeNode
}

type traversalFunc func(*TreeNode)

func recoverTree(root *TreeNode) {
if root == nil {
return
}

rNode := &RecoverNode{}
tfunc := func(rnode *RecoverNode) traversalFunc {
return func(node *TreeNode) {
recoverFunc(node, rnode)
}
}(rNode)
inorderTraversal(root, tfunc)
if rNode.Is_recover == 0 && rNode.Illegal != nil {
rNode.Pre.Val, rNode.Illegal.Val = rNode.Illegal.Val, rNode.Pre.Val
}
}

func inorderTraversal(root *TreeNode, tfunc traversalFunc) {
if root == nil {
return
}

inorderTraversal(root.Left, tfunc)
tfunc(root)
inorderTraversal(root.Right, tfunc)
}

func recoverFunc(node *TreeNode, rnode *RecoverNode) {
if node == nil {
return
}

if rnode.Is_recover == 1 {
return
}

if rnode.Pre == nil {
rnode.Pre = node
return
}

if node.Val < rnode.Pre.Val {
if rnode.Illegal == nil {
rnode.Illegal = rnode.Pre
} else {
rnode.Illegal.Val, node.Val = node.Val, rnode.Illegal.Val
rnode.Is_recover = 1
}
} else {
if rnode.Illegal != nil {
if rnode.Illegal.Val < node.Val {
rnode.Illegal.Val, rnode.Pre.Val = rnode.Pre.Val, rnode.Illegal.Val
rnode.Is_recover = 1
}
}
}

rnode.Ppre = rnode.Pre
rnode.Pre = node
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func main() {
s := &TreeNode{
Val: 2,
Left: &TreeNode{
Val: 3,
},
Right: &TreeNode{
Val: 1,
},
}

fmt.Println(tree2str(s))
recoverTree(s)
fmt.Println(tree2str(s))
}

3.8 delete node

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
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func deleteNode(root *TreeNode, key int) *TreeNode {
if root == nil {
return nil
}

if root.Val == key {
if root.Left == nil || root.Right == nil {
if root.Left != nil {
return root.Left
} else if root.Right != nil {
return root.Right
} else {
return nil
}
} else {
successor := treeMinimum(root.Right)
root.Val = successor.Val
root.Right = deleteNode(root.Right, successor.Val)
}
}

if root.Val < key {
root.Right = deleteNode(root.Right, key)
} else {
root.Left = deleteNode(root.Left, key)
}
return root
}

func treeMinimum(node *TreeNode) *TreeNode {
if node.Left != nil {
return treeMinimum(node.Left)
} else {
return node
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func main() {
s := &TreeNode{
Val: 2,
Left: &TreeNode{
Val: 1,
},
Right: &TreeNode{
Val: 3,
},
}

fmt.Println(tree2str(s))
s = deleteNode(s, 1)
fmt.Println(tree2str(s))
}

3.9 convert sorted list to bst

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
type ListNode struct {
Val int
Next *ListNode
}

type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}

func sortedListToBST(head *ListNode) *TreeNode {
if head == nil {
return nil
}
length := getListLength(head)
return sortedListToBSTHelper(head, length)
}

func getListLength(head *ListNode) int {
if head == nil {
return 0
}

return 1 + getListLength(head.Next)
}

func getListNth(head *ListNode, nth int) *ListNode {
if head == nil {
return nil
}
if nth < 1 {
return head
}

return getListNth(head.Next, nth-1)
}

func sortedListToBSTHelper(head *ListNode, length int) *TreeNode {
if length < 1 {
return nil
}

if length == 1 {
return &TreeNode{
Val: head.Val,
}
}

if length == 1 {
return &TreeNode{
Val: head.Val,
Right: &TreeNode{
Val: head.Next.Val,
},
}
}

mid := length / 2
mid_node := getListNth(head, mid)
return &TreeNode{
Val: mid_node.Val,
Left: sortedListToBSTHelper(head, mid),
Right: sortedListToBSTHelper(mid_node.Next, length-1-mid),
}
}
1
2
3
4
5
6
7
8
9
10
11
12
func main() {
sortedLst := &ListNode{
Val: 1,
Next: &ListNode{
Val:2,
Next: &ListNode{
Val:3,
},
},
}
fmt.Println(tree2str(sortedListToBST(sortedLst)))
}

3.10 kth smallest elemen

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
type KthNode struct {
K int
Val int
}

type traversalFunc func(*TreeNode)

func kthSmallest(root *TreeNode, k int) int {
if root == nil {
return 0
}

kNode := &KthNode{K: k}
tfunc := func(knode *KthNode) traversalFunc {
return func(node *TreeNode) {
kthFunc(node, knode)
}
}(kNode)
inorderTraversal(root, tfunc)
return kNode.Val
}

func inorderTraversal(root *TreeNode, tfunc traversalFunc) {
if root == nil {
return
}

inorderTraversal(root.Left, tfunc)
tfunc(root)
inorderTraversal(root.Right, tfunc)
}

func kthFunc(node *TreeNode, kn *KthNode) {
if node == nil && kn.K == 0 {
return
}

kn.K -= 1
if kn.K == 0 {
kn.Val = node.Val
}
return
}
1
2
3
4
5
6
7
8
9
10
11
func main() {
t := &TreeNode{
Val: 3,
Left: &TreeNode{Val: 2},
Right: &TreeNode{Val: 5},
}

fmt.Println(kthSmallest(t,1))
fmt.Println(kthSmallest(t,2))
fmt.Println(kthSmallest(t,3))
}

3.11 unique bst

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func numTrees(n int) int {
if n < 1 {
return 1
}

ctl_arr := make([]int, n+1)
ctl_arr[0] = 1
ctl_arr[1] = 1
for i := 2; i < n+1; i += 1 {
for j := 0; j < i; j += 1 {
ctl_arr[i] += ctl_arr[j] * ctl_arr[i-j-1]
}
}

return ctl_arr[n]
}
1
2
3
4
5
func main() {
for _, n := range list{
fmt.Println(numTrees(n))
}
}

3.12 unique bst II

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
func generateTrees(n int) []*TreeNode {
if n == 0 {
return []*TreeNode{}
}

tree_arr := []*TreeNode{
&TreeNode{
Val: 1,
},
}

for i := 2; i <= n; i += 1 {
ng_tree_arr := make([]*TreeNode, 0)
for index, _ := range tree_arr {
tree := tree_arr[index]
ng_tree_arr = append(ng_tree_arr, genTreesHelper(tree, i)...)
}
tree_arr = ng_tree_arr
}

return tree_arr
}

func genTreesHelper(root *TreeNode, greater int) []*TreeNode {
if root == nil {
return []*TreeNode{}
}

cr := cloneTree(root)
right := cr
var parent *TreeNode
tree_arr := make([]*TreeNode, 0)
for {
if right != nil {
rval := right.Val
node := &TreeNode{
Val: greater,
Left: right,
}
if parent != nil {
parent.Right = node
} else {
cr = node
}
tree_arr = append(tree_arr, cr)

cr = cloneTree(root)
parent = getNode(cr, rval)
right = parent.Right
} else {
parent.Right = &TreeNode{Val: greater}
tree_arr = append(tree_arr, cr)
break
}
}

return tree_arr
}

func cloneTree(root *TreeNode) *TreeNode {
if root == nil {
return nil
}

return &TreeNode{
Val: root.Val,
Left: cloneTree(root.Left),
Right: cloneTree(root.Right),
}
}

func getNode(root *TreeNode, val int) *TreeNode {
if root == nil {
return nil
}

if root.Val == val {
return root
}

if root.Val < val {
return getNode(root.Right, val)
} else {
return getNode(root.Left, val)
}
}
1
2
3
4
5
6
func main() {
for _, n := range list{
tree_arr := generateTrees(n)
fmt.Println(n, len(tree_arr))
}
}
Last Updated 2017-07-16 Sun 15:30.
Render by hexo-renderer-org with Emacs 25.3.2 (Org mode 8.2.10)