TalkGo算法之美第三期系列一开始啦。
本期主题以树为主，本系列为期一周，会挑选一些树的基本题目来进行练手，并不会太难，主要目的是重温下树的一些基本操作。
先重温下二叉树是怎么构造出来的吧
108. 将有序数组转换为二叉搜索树
附加题：
95. 不同的二叉搜索树 II
Tips:递归
前中后序遍历，尝试使用递归以及非递归形式写一遍。
层次遍历
附加题：
// 108
func sortedArrayToBST(nums []int) *TreeNode {
return helper(nums, 0, len(nums) - 1)
}
func helper(nums []int, left, right int) *TreeNode {
if right < left {
return nil
}
if left == right {
return &TreeNode{Val: nums[left]}
}
mid := (left + right) / 2
return &TreeNode{Val: nums[mid], Left: helper(nums, left, mid - 1),
Right: helper(nums, mid + 1, right)}
}
// 95
func generateTrees(n int) []*TreeNode {
if n < 1 {
return nil
}
return helper(1, n)
}
func helper(start, end int) []*TreeNode {
if start > end {
return []*TreeNode{nil}
}
res := make([]*TreeNode, 0, end-start)
for i := start; i <= end; i++ {
lefts := helper(start, i-1)
rights := helper(i+1, end)
for _, left := range lefts {
for _, right := range rights {
res = append(res, &TreeNode{Val: i, Left: left, Right: right})
}
}
}
return res
}
// 144. 递归
func preorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
res := make([]int, 0, 8)
res = append(res, root.Val)
res = append(res, preorderTraversal(root.Left)...)
res = append(res, preorderTraversal(root.Right)...)
return res
}
// 144. 迭代
func preorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
stack := make([]*TreeNode, 0, 8)
stack = append(stack, root)
res := make([]int, 0, 8)
for len(stack) > 0 {
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, root.Val)
if root.Right != nil {
stack = append(stack, root.Right)
}
if root.Left != nil {
stack = append(stack, root.Left)
}
}
return res
}
// 94. 递归
func inorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
res := make([]int, 0, 8)
res = append(res, inorderTraversal(root.Left)...)
res = append(res, root.Val)
res = append(res, inorderTraversal(root.Right)...)
return res
}
// 94. 迭代
func inorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
stack := make([]*TreeNode, 0, 8)
res := make([]int, 0, 8)
for len(stack) > 0 || root != nil {
for root != nil {
stack = append(stack, root)
root = root.Left
}
root = stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, root.Val)
root = root.Right
}
return res
}
// 145 递归
func postorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
res := make([]int, 0, 8)
res = append(res, postorderTraversal(root.Left)...)
res = append(res, postorderTraversal(root.Right)...)
res = append(res, root.Val)
return res
}
/*
- 出栈一个节点，加入输出
- 一路向左，输出当前节点，并把当前节点右节点入栈
*/
func preorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
res := make([]int, 0)
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
head := queue[len(queue)-1]
queue = queue[:len(queue)-1]
//一路向左边遍历
for head != nil {
res = append(res, head.Val)
if head.Right != nil {
queue = append(queue, head.Right)
}
head = head.Left
}
}
return res
}
func preorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
res := make([]int, 0)
queue := make([]*TreeNode, 0)
// queue = append(queue, root)
cur := root
for {
//一路向左边遍历，返回当前的val，加入节点的右节点
for cur != nil {
res = append(res, cur.Val)
if cur.Right != nil {
queue = append(queue, cur.Right)
}
cur = cur.Left
}
if len(queue) == 0 {
return res
}
//出栈
cur = queue[len(queue)-1]
queue = queue[:len(queue)-1]
}
return res
}
/*. 二叉树的中序遍历
- 1. 一路向左入栈
- 2. 到达最左边后，出栈保存，把当前节点的右子节点作为当前节点，回到第一步
*/
func inorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
stack := make([]*TreeNode, 0)
result := make([]int, 0)
cur := root
for {
// - 1. 一路向左入栈
for cur != nil {
stack = append(stack, cur)
cur = cur.Left
}
if len(stack) == 0 {
return result
}
// - 2. 到达最左边后，出栈保存，把当前节点的右子节点作为当前节点，回到第一步
cur = stack[len(stack)-1]
stack = stack[:len(stack)-1]
result = append(result, cur.Val)
cur = cur.Right
}
return result
}
颜色标记法
/*
使用颜色标记节点的状态，新节点为白色，已访问的节点为灰色。
如果遇到的节点为白色，则将其标记为灰色，然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色，则将节点的值输出。
*/
func postorderTraversal(root *TreeNode) []int {
if root == nil {
return nil
}
result := make([]int, 0)
stack := make([]*Node, 0)
stack = append(stack, &Node{root, false})
skLen := 1
for {
if skLen == 0 {
return result
}
cur := stack[skLen-1]
/*
我认为颜色标记法的核心就在于新增了一个标记 来标记当前节点是否是从左边节点出栈过来的 还是从右边节点出栈过来的，然后做出下一步操作
*/
if !cur.color {
cur.color = true
if cur.Node.Right != nil {
stack = append(stack, &Node{cur.Node.Right, false})
skLen++
}
if cur.Node.Left != nil {
stack = append(stack, &Node{cur.Node.Left, false})
skLen++
}
} else {
result = append(result, cur.Node.Val)
stack = stack[:skLen-1]
skLen--
}
}
}
第108题
func sortedArrayToBST(nums []int) *TreeNode {
if len(nums) <= 0 {
return nil
}
mid := len(nums) / 2
root := &TreeNode{nums[mid], nil, nil}
root.Left = sortedArrayToBST(nums[:mid])
root.Right = sortedArrayToBST(nums[mid+1:])
return root
}
第95题
func generateTrees(n int) (ans []*TreeNode) {
if n == 0 {
return nil
}
return helper(1, n)
}
func helper(l, r int) []*TreeNode {
if l > r {
return []*TreeNode{nil}
}
res := []*TreeNode{}
for i := l; i <= r; i++ {
leftTreeList := helper(l, i - 1)
rightTreeList := helper(i + 1, r)
for _, left := range leftTreeList {
for _, right := range rightTreeList {
root := &TreeNode{Val : i, Left : nil, Right : nil}
root.Left = left
root.Right = right
res = append(res, root)
}
}
}
return res
}
第144题
// 前序
func preorderTraversal(root *TreeNode) (ans []int) {
ptr := root
stack := []*TreeNode{}
for ptr != nil || len(stack) > 0 {
if ptr != nil {
ans = append(ans, ptr.Val)
stack = append(stack, ptr)
ptr = ptr.Left
} else {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
ptr = top.Right
}
}
return
}
第94题
// 中序
func inorderTraversal(root *TreeNode) (ans []int) {
ptr := root
stack := []*TreeNode{}
for ptr != nil || len(stack) > 0 {
if ptr != nil {
stack = append(stack, ptr)
ptr = ptr.Left
} else {
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
ans = append(ans, top.Val)
ptr = top.Right
}
}
return
}
第145题
// 后序
func postorderTraversal(root *TreeNode) (ans []int) {
ptr := root
stack := []*TreeNode{}
var pre *TreeNode
for ptr != nil || len(stack) > 0 {
if ptr != nil {
stack = append(stack, ptr)
ptr = ptr.Left
} else {
top := stack[len(stack)-1]
if top.Right != nil && top.Right != pre {
ptr = top.Right
} else {
ans = append(ans, top.Val)
stack = stack[:len(stack)-1]
pre = top
}
}
}
return
}
第102题
func levelOrder(root *TreeNode) (ans [][]int) {
if root == nil {
return nil
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
n := 1
for len(queue) > 0 {
comb := make([]int, 0)
for i := 0; i < n; i++ {
front := queue[0]
queue = queue[1:]
if front.Left != nil {
queue = append(queue, front.Left)
}
if front.Right != nil {
queue = append(queue, front.Right)
}
comb = append(comb, front.Val)
}
ans = append(ans, comb)
n = len(queue)
}
return
}
第103题
func zigzagLevelOrder(root *TreeNode) (ans [][]int) {
if root == nil {
return nil
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
n := 1
level := 1
for len(queue) > 0 {
comb := make([]int, 0)
for i := 0; i < n; i++ {
front := queue[0]
queue = queue[1:]
if front.Left != nil {
queue = append(queue, front.Left)
}
if front.Right != nil {
queue = append(queue, front.Right)
}
comb = append(comb, front.Val)
}
if level % 2 == 0 {
for i, n := 0, len(comb); i < n/2; i++ {
comb[i], comb[n-1-i] = comb[n-1-i], comb[i]
}
}
ans = append(ans, comb)
n = len(queue)
level++
}
return
}
第429题
func levelOrder(root *Node) (ans [][]int) {
if root == nil {
return nil
}
queue := make([]*Node, 0)
queue = append(queue, root)
curLen := 1
for len(queue) > 0 {
comb := make([]int, 0)
for i := 0; i < curLen; i++ {
front := queue[0]
queue = queue[1:]
comb = append(comb, front.Val)
for _, child := range front.Children {
if child != nil {
queue = append(queue, child)
}
}
}
ans = append(ans, append([]int(nil), comb...))
curLen = len(queue)
}
return
}
func preorderTraversal(root *TreeNode) (vals []int) {
if root == nil {
return
}
vals = append(vals, root.Val)
vals = append(vals, preorderTraversal(root.Left)...)
vals = append(vals, preorderTraversal(root.Right)...)
return
}
var res []int
func preorderTraversal(root *TreeNode) []int {
res = []int{}
dfs(root)
return res
}
func dfs(root *TreeNode) {
if root != nil {
res = append(res, root.Val)
dfs(root.Left)
dfs(root.Right)
}
}
func preorderTraversal(root *TreeNode) (vals []int) {
var preorder func(*TreeNode)
preorder = func(node *TreeNode) {
if node == nil {
return
}
vals = append(vals, node.Val)
preorder(node.Left)
preorder(node.Right)
}
preorder(root)
return
}
func preorderTraversal(root *TreeNode) []int {
var res []int
var stack []*TreeNode
for root != nil || len(stack) > 0 {
for root != nil {
res = append(res, root.Val)
stack = append(stack, root.Right)
root = root.Left
}
top := len(stack)-1
root = stack[top]
stack = stack[:top]
}
return res
}
func preorderTraversal(root *TreeNode) (vals []int ){
var stack []*TreeNode
node := root
for node != nil || len(stack) > 0 {
for node != nil {
vals = append(vals, node.Val)
stack = append(stack, node)
node = node.Left
}
node = stack[len(stack)-1].Right
stack = stack[:len(stack)-1]
}
return
}
思路与算法
有一种巧妙的方法可以在线性时间内，只占用常数空间来实现前序遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出，因此被称为 Morris 遍历。
Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其前序遍历规则总结如下：
func preorderTraversal(root *TreeNode) []int {
var max *TreeNode
var res []int
for root != nil {
if root.Left == nil {
res = append(res, root.Val)
root = root.Right
} else {
max = root.Left
for max.Right != nil && max.Right != root {
max = max.Right
}
if max.Right == nil {
res = append(res, root.Val)
max.Right = root.Right
root = root.Left
} else {
root = root.Right
max.Right = nil
}
}
}
return res
}
func preorderTraversal(root *TreeNode) []int {
var max *TreeNode
var res []int
for root != nil {
if root.Left == nil {
res = append(res, root.Val)
root = root.Right
} else {
max = root.Left
for max.Right != nil {
max = max.Right
}
root.Right, max.Right = root.Left, root.Right
root.Left = nil
}
}
return res
}
/*
4
/ \
1 5
/ \ / \
2 3 6 7
4
\
1
/ \
2 3 -> 5
/ \
6 7
1
/ \
2 3 -> 5
/ \
6 7
res = [4]
1
2
\
3 -> 5
/ \
6 7
res = [4,1]
*/
当前节点 cur, 一开始 cur 指向树根
先序遍历：能回自己2次的节点第2次打印，不能的第1次遇见打印
中序遍历：向右移动，打印
后序遍历：反转链表
func preorderTraversal(root *TreeNode) (vals []int) {
var p1, p2 *TreeNode = root, nil
for p1 != nil {
p2 = p1.Left//判断有当前节点有没有左树
if p2 != nil {//2.有左树
//b.找到 cur 左树真实的最右节点，第2次
for p2.Right != nil && p2.Right != p1 {
p2 = p2.Right
}
//p2一定是左树上最右节点
if p2.Right == nil {//a.第1次来到cur
vals = append(vals, p1.Val)
p2.Right = p1
p1 = p1.Left
continue
}//else p2.Right == p1
p2.Right = nil
} else {//1.无左树，当前节点向右移动
vals = append(vals, p1.Val)
}
p1 = p1.Right
}
return
}
var res []int
func inorderTraversal(root *TreeNode) []int {
res = []int {}
dfs(root)
return res
}
func dfs(root *TreeNode) {
if root != nil {
dfs(root.Left)
res = append(res, root.Val)
dfs(root.Right)
}
}
func inorderTraversal(root *TreeNode) []int {
res := []int {}
if root != nil {
res = append(res, inorderTraversal(root.Left)...)
res = append(res, root.Val)
res = append(res, inorderTraversal(root.Right)...)
}
return res
}
var res []int
func postorderTraversal(root *TreeNode) []int {
res = []int{}
dfs(root)
return res
}
func dfs(root *TreeNode) {
if root != nil {
dfs(root.Left)
dfs(root.Right)
res = append(res, root.Val)
}
}
周一:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
// 主要思路:
// 1. 确定根节点为数组中间值
// 2. 递归构造左右子树
// 3. 维护根节点和左右子树之间的关系
return build(0, nums.length - 1, nums);
}
public TreeNode build(int l, int r, int[] nums) {
if(l > r) return null;
int mid;
mid = (l + r) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = build(l, mid - 1, nums);
root.right = build(mid + 1, r, nums);
return root;
}
}
func levelOrder(root *TreeNode) [][]int {
if root == nil {
return nil
}
result := make([][]int, 0)
s := make([]*TreeNode, 0) //队列
s = append(s, root)
sLen := 1 //当前层的长度
for {
if sLen == 0 {
return result
}
tmpResult := make([]int, sLen) //当前层遍历结果
tmpLen := 0 //下一层的长度
for i := 0; i < sLen; i++ { //遍历当前层
tmpResult[i] = s[i].Val
if s[i].Left != nil {
s = append(s, s[i].Left)
tmpLen++
}
if s[i].Right != nil {
s = append(s, s[i].Right)
tmpLen++
}
}
result = append(result, tmpResult)
s = s[sLen:]
sLen = tmpLen
}
}
/*
https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
*/
// 相比102 就多一个方向的标记
/*
if zig {
tmpResult[i] = s[i].Val
} else {
tmpResult[i] = s[sLen-1-i].Val
}
*/
func zigzagLevelOrder(root *TreeNode) [][]int {
if root == nil {
return nil
}
result := make([][]int, 0)
s := make([]*TreeNode, 0) //队列
s = append(s, root)
sLen := 1 //当前层的长度
zig := true
for {
if sLen == 0 {
return result
}
tmpResult := make([]int, sLen) //当前层遍历结果
tmpLen := 0 //下一层的长度
for i := 0; i < sLen; i++ { //遍历当前层
if zig {
tmpResult[i] = s[i].Val
} else {
tmpResult[i] = s[sLen-1-i].Val
}
if s[i].Left != nil {
s = append(s, s[i].Left)
tmpLen++
}
if s[i].Right != nil {
s = append(s, s[i].Right)
tmpLen++
}
}
result = append(result, tmpResult)
s = s[sLen:]
sLen = tmpLen
zig = !zig
}
}
func levelOrder(root *Node) [][]int {
//BFS
if root == nil {
return nil
}
res := make([][]int, 0)
cur := []*Node{root}
res = append(res, []int{root.Val})
for len(cur) > 0 {
tmp := make([]*Node, 0)
tmpV := make([]int, 0)
for _, v := range cur {
for _, vc := range v.Children {
tmp = append(tmp, vc)
tmpV = append(tmpV, vc.Val)
}
}
//当前层遍历结束后
if len(tmpV) > 0 {
res = append(res, tmpV)
}
cur = tmp
}
return res
}
var res [][]int
func levelOrder(root *TreeNode) [][]int {
res = [][]int{}
dfs(root, 0)
return res
}
func dfs(root *TreeNode, level int) {
if root != nil {
if len(res) == level {
res = append(res, []int{})
}
res[level] = append(res[level], root.Val)
dfs(root.Left, level+1)
dfs(root.Right, level+1)
}
}
func levelOrder(root *TreeNode) [][]int {
return dfs(root, 0, [][]int{})
}
func dfs(root *TreeNode, level int, res [][]int) [][]int {
if root == nil {
return res
}
if len(res) == level {
res = append(res, []int{root.Val})
} else {
res[level] = append(res[level], root.Val)
}
res = dfs(root.Left, level+1, res)
res = dfs(root.Right, level+1, res)
return res
}
func levelOrder(root *TreeNode) [][]int {
res := [][]int{}
if root == nil {
return res
}
queue := []*TreeNode{root}
for level := 0; 0 < len(queue); level ++ {
res = append(res, []int{})
next := []*TreeNode{}
for j := 0; j < len(queue); j ++ {
node := queue[j]
res[level] = append(res[level], node.Val)
if node.Left != nil {
next = append(next, node.Left)
}
if node.Right != nil {
next = append(next, node.Right)
}
}
queue = next
}
return res
}
func levelOrder(root *TreeNode) [][]int {
res := [][]int {}
if root == nil {
return res
}
queue := [] *TreeNode{root}
level := 0
for {
counter := len(queue)
if counter == 0 {
break
}
res = append(res, []int{})
for 0 < counter {
counter --
res[level] = append(res[level], queue[0].Val)
if queue[0].Left != nil {
queue = append(queue, queue[0].Left)
}
if queue[0].Right != nil {
queue = append(queue, queue[0].Right)
}
queue = queue[1:]
}
level ++
}
return res
}
##附加题：
103. 二叉树的锯齿形层序遍历
var res [][]int
func zigzagLevelOrder(root *TreeNode) [][]int {
res = [][]int{}
dfs(root, 0)
return res
}
func dfs(root *TreeNode, level int) {
if root != nil {
if len(res) == level {
res = append(res, []int{})
}
if level % 2 == 0 {//奇数层，追加到结尾
res[level] = append(res[level], root.Val)
} else {//偶数层，逆序(root.Val 添加到 res 开头)
res[level] = append([]int{root.Val}, res[level]...)
}
dfs(root.Left, level+1)
dfs(root.Right, level+1)
}
}
/**
* Definition for a Node.
* type Node struct {
* Val int
* Children []*Node
* }
*/
var res [][]int
func levelOrder(root *Node) [][]int {
res = [][]int {}
if root == nil {
return res
}
queue := []*Node {root}
for level := 0; 0 < len(queue); level ++ {
res = append(res, []int{})
next := []*Node {}
for j := 0; j < len(queue); j ++ {
node := queue[j]
res[level] = append(res[level], node.Val)
for _,n := range node.Children {
next = append(next, n)
}
}
queue = next
}
return res
}