2

Leetcode-tree

 2 years ago
source link: https://brantou.github.io/2017/07/16/leetcode-tree/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

<!– more –>

1 binary tree traversal

1.1 level order

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
}
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

<<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
}
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

  <<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
}
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

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)...)
}
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

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)...)
}
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

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)
}
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

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}
struct TreeLinkNode {
 int val;
 TreeLinkNode *left, *right, *next;
 TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

2.1 max depth

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))
}
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

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
}
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

<<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)
}
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

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
}
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

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)
}
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

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

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)
}
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

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)
}
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

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
  }
}
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

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;
  }
};
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

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);
 */
func main() {
  trie := Constructor()
  trie.Insert("hello")
  fmt.Println(trie.Search("hello"))
  fmt.Println(trie.StartsWith("hello"))
}

2.12 merge two binary tree

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),
  }
}
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

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
}
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

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
}
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

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
}
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

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
}
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

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
}
func main() {
  t := &TreeNode{
    Val: 1,
    Left: &TreeNode{Val: 3},
    Right: &TreeNode{Val: 5},
  }

fmt.Println(largestValues(t))
}

2.18 most frequent subtree sum

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
}
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

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
}
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

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
}
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

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;
  }
};
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

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
}
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

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;
  }
};
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

<<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);
  }
};
 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

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
}
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.1 BSTIterator

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();
 */
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

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)
}
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

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)
}
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

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)...)
}
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

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:]),
  }
}
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

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;
  }
};
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

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
}
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

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
  }
}
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

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),
  }
}
func main() {
  sortedLst := &ListNode{
    Val: 1,
    Next: &ListNode{
      Val:2,
      Next: &ListNode{
	Val:3,
      },
    },
  }
  fmt.Println(tree2str(sortedListToBST(sortedLst)))
}

3.10 kth smallest elemen

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
}
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

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]
}
func main() {
  for _, n := range list{
    fmt.Println(numTrees(n))
  }
}

3.12 unique bst II

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)
  }
}
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)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK