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)