树
遍历
leetcode 94, 144, 145 easy
func inorderTraversal(root *TreeNode) []int {
arr := []int{}
var helper func(*TreeNode)
helper = func(root *TreeNode) {
if root == nil {return}
helper(root.Left)
arr = append(arr, root.Val)
helper(root.Right)
}
helper(root)
return arr
}
N叉树的层序遍历
leetcode 429
func levelOrder(root *Node) [][]int {
res := [][]int{}
if root == nil {return res}
q := []*Node{root}
for len(q) > 0 {
length := len(q)
tmp := make([]int, length)
for i := 0; i < length; i++ {
node := q[i]
tmp[i] = node.Val
for _, c := range node.Children {
q = append(q, c)
}
}
q = q[length:]
res = append(res, tmp)
}
return res
}
N叉树的前/后序遍历
func preorder(root *Node) []int {
res := []int{}
var helper func(root *Node)
helper = func(root *Node) {
if root == nil {return}
res = append(res, root.Val)
for _, n := range root.Children {
helper(n)
}
}
helper(root)
return res
}
二叉树的垂序遍历
我们可以从根节点开始，对整棵树进行一次遍历，在遍历的过程中使用数组 nodes 记录下每个节点的行号列号以及值 。在遍历完成后，我们按照 col 为第一关键字升序，row 为第二关键字升序，value 为第三关键字升序，对所有的节点进行排序即可。
type data struct{ col, row, val int }
func verticalTraversal(root *TreeNode) (ans [][]int) {
nodes := []data{}
var dfs func(*TreeNode, int, int)
dfs = func(node *TreeNode, row, col int) {
if node == nil {
return
}
nodes = append(nodes, data{col, row, node.Val})
dfs(node.Left, row+1, col-1)
dfs(node.Right, row+1, col+1)
}
dfs(root, 0, 0)
sort.Slice(nodes, func(i, j int) bool {
a, b := nodes[i], nodes[j]
return a.col < b.col || a.col == b.col && (a.row < b.row || a.row == b.row && a.val < b.val)
})
lastCol := math.MinInt32
for _, node := range nodes {
if node.col != lastCol {
lastCol = node.col
ans = append(ans, nil)
}
ans[len(ans)-1] = append(ans[len(ans)-1], node.val)
}
return
}