1.前序

  1. /**
  2.  * Definition for a binary tree node.
  3.  * type TreeNode struct {
  4.  *     Val int
  5.  *     Left *TreeNode
  6.  *     Right *TreeNode
  7.  * }
  8.  */ 
  9. func preorderTraversal(root *TreeNode) []int {
  10.   res := []int{}
  11.   if root == nil {
  12.     return res
  13.   }
  14.   stack := []*TreeNode{}
  15.   cur := root
  16.   for len(stack) > 0 || cur != nil {
  17.     for cur != nil {
  18.       res = append(res, cur.Val)
  19.       stack= append(stack, cur)
  20.       cur = cur.Left
  21.     }
  22.     temp := stack[len(stack) -1]
  23.     stack = stack[:len(stack) -1]
  24.     cur = temp.Right
  25.   }
  26.   return res
  27. }

2.中序

  1. /**
  2.  * Definition for a binary tree node.
  3.  * type TreeNode struct {
  4.  *     Val int
  5.  *     Left *TreeNode
  6.  *     Right *TreeNode
  7.  * }
  8.  */
  9. func inorderTraversal(root *TreeNode) []int {
  10.   res := []int{}
  11.   if root == nil {
  12.     return res
  13.   }
  14.   stack := []*TreeNode{}
  15.   cur := root
  16.   for len(stack) > 0 || cur != nil {
  17.     for cur != nil {
  18.       stack = append(stack, cur)
  19.       cur = cur.Left
  20.     }
  21.     temp := stack[len(stack) -1]
  22.     stack = stack[:len(stack) -1]
  23.     res = append(res, temp.Val)
  24.     cur = temp.Right
  25.   }
  26.   return res
  27. }

3. 后序

  1. /**
  2.  * Definition for a binary tree node.
  3.  * type TreeNode struct {
  4.  *     Val int
  5.  *     Left *TreeNode
  6.  *     Right *TreeNode
  7.  * }
  8.  */
  9. func postorderTraversal(root *TreeNode) []int {
  10.   res := []int{}
  11.   if root == nil {
  12.     return res
  13.   }
  14.   stack := []*TreeNode{}
  15.   flagMap := make(map[*TreeNode]int)
  16.   cur := root
  17.   for len(stack) >0 || cur != nil {
  18.     for cur != nil {
  19.       stack = append(stack,cur)
  20.       flagMap[cur] = 1
  21.       cur = cur.Left
  22.     }
  23.     temp := stack[len(stack) -1]
  24.     if flagMap[temp] == 1 {
  25.       flagMap[temp] ++
  26.       cur = temp.Right
  27.     } else {
  28.       res = append(res, temp.Val)
  29.       stack = stack[:len(stack) -1]
  30.     }
  31.   }
  32.   return res

4. 层序

  1. /**
  2.  * Definition for a binary tree node.
  3.  * type TreeNode struct {
  4.  *     Val int
  5.  *     Left *TreeNode
  6.  *     Right *TreeNode
  7.  * }
  8.  */
  9. func levelOrder(root *TreeNode) [][]int {
  10.    res := [][]int{}
  11.   if root == nil {
  12.     return res
  13.   }
  14.   queue := []*TreeNode{}
  15.   queue = append(queue, root)  
  16.   for len(queue) > 0 {
  17.     size := len(queue)
  18.     level := []int{}
  19.     for size > 0 {
  20.       cur := queue[0]
  21.       queue = queue[1:]
  22.       level = append(level, cur.Val)
  23.       if cur.Left != nil {
  24.         queue = append(queue, cur.Left)
  25.       }
  26.       if cur.Right != nil {
  27.         queue = append(queue, cur.Right)
  28.       }
  29.       size --
  30.     }
  31.     res = append(res, level)
  32.   }
  33.   return res
  34. }

5. 是否是镜像树

  1. func isSymmetric(root *TreeNode) bool {
  2.   if root == nil {
  3.     return true
  4.   }
  5.   return isSameTree(root.Left, mirrorTree(root.Right))
  6. }
  8. func mirrorTree(node *TreeNode) *TreeNode {
  9.   if node == nil {
  10.     return nil
  11.   }
  12.   tmp := node.Left
  13.   node.Left = mirrorTree(node.Right)
  14.   node.Right= mirrorTree(tmp)
  15.   return node
  16. }
  18. func isSameTree(A, B *TreeNode)bool {
  19.   if A == nil && B == nil {
  20.     return true
  21.   }else  if A == nil || B == nil {
  22.     return false
  23.   } else if  A.Val == B.Val {
  24.     return isSameTree(A.Left, B.Left) && isSameTree(A.Right, B.Right)
  25.   }
  26.   return false
  27. }
  1. func isSymmetric(root *TreeNode) bool {
  2.   if root == nil {
  3.     return true
  4.   }
  5.   return recursion(root.Left, root.Right)
  6. }
  8. func recursion(A, B *TreeNode) bool {
  9.   if A == nil && B == nil {
  10.     return true
  11.   }
  12.   if  A == nil || B == nil || A.Val != B.Val {
  13.     return false
  14.   }
  15.   return recursion(A.Left, B.Right) && recursion(A.Right, B.Left)
  16. }