二叉树的基本结构是
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