0%

Tree

二叉树的基本结构是

1
2
3
4
5
6
// TreeNode 树节点
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