二叉树的基本结构是
1 2 3 4 5 6
| type TreeNode struct { Val int Left *TreeNode Right *TreeNode }
|
前中后序遍历
1 2 3 4 5 6 7 8 9 10
| func traverse(root *TreeNode) { if root == nil { return; } traverse(root.left); traverse(root.right); }
|
需要做啥,只需要在对应位置插入操作即可
非递归
前序、后序
后序代码如下,考虑到递归都是使用的栈,这里也需要用栈来实现。使用两个栈,因为每次压入都是先左再右,弹出的时候都是先右后左,所以需要额外一个栈去接收。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| func postorderTraversal(root *TreeNode) []int { if root == nil{ return nil } var ans []int var stack []*TreeNode stack = append(stack, root) for len(stack) != 0{ node := stack[len(stack)-1] stack = stack[:len(stack)-1] if node.Left != nil{ stack =append(stack, node.Left) } if node.Right != nil{ stack = append(stack, node.Right) } ans = append(ans, node.Val) } for i := 0; i < len(ans)/2; i++{ ans[i], ans[len(ans)-i-1] = ans[len(ans)-i-1], ans[i] } return ans }
|
前序因为只是根的位置不同,把ans append提前,然后在压栈的时候先压right,再压left即可。最后不需要翻转
中序
// TODO