TalkGo算法之美第三期系列一

TalkGo算法之美第三期系列一开始啦。
本期主题以树为主,本系列为期一周,会挑选一些树的基本题目来进行练手,并不会太难,主要目的是重温下树的一些基本操作。

周一:树的构造

树的构造

先重温下二叉树是怎么构造出来的吧
108. 将有序数组转换为二叉搜索树

附加题:
95. 不同的二叉搜索树 II
Tips:递归

周三:树的遍历

前中后序遍历,尝试使用递归以及非递归形式写一遍。

144. 二叉树的前序遍历
94. 二叉树的中序遍历
145. 二叉树的后序遍历

周五:树的遍历

层次遍历

102. 二叉树的层序遍历

附加题:

103. 二叉树的锯齿形层序遍历
429. N 叉树的层序遍历
5赞
// 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
}

144

题解



/*

- 出栈一个节点,加入输出
- 一路向左,输出当前节点,并把当前节点右节点入栈
*/

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
}


144 另外稍微不同的写法


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
}


94


/*. 二叉树的中序遍历
- 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
}


145题

颜色标记法


/*
使用颜色标记节点的状态,新节点为白色,已访问的节点为灰色。
如果遇到的节点为白色,则将其标记为灰色,然后将其右子节点、自身、左子节点依次入栈。
如果遇到的节点为灰色,则将节点的值输出。
*/
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
}
3赞

144. 二叉树的前序遍历

方法一:递归

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
}

方法三:Morris 遍历

思路与算法

有一种巧妙的方法可以在线性时间内,只占用常数空间来实现前序遍历。这种方法由 J. H. Morris 在 1979 年的论文「Traversing Binary Trees Simply and Cheaply」中首次提出,因此被称为 Morris 遍历。

Morris 遍历的核心思想是利用树的大量空闲指针,实现空间开销的极限缩减。其前序遍历规则总结如下:

  1. 新建临时节点,令该节点为 root;
  2. 如果当前节点的左子节点为空,将当前节点加入答案,并遍历当前节点的右子节点;
  3. 如果当前节点的左子节点不为空,在当前节点的左子树中找到当前节点在中序遍历下的前驱节点:
    a: 如果前驱节点的右子节点为空,将前驱节点的右子节点设置为当前节点。然后将当前节点加入答案,并将前驱节点的右子节点更新为当前节点。当前节点更新为当前节点的左子节点。
    b: 如果前驱节点的右子节点为当前节点,将它的右子节点重新设为空。当前节点更新为当前节点的右子节点。
  4. 重复步骤 2 和步骤 3,直到遍历结束。
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
}

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 = 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] 
*/

Morris序

当前节点 cur, 一开始 cur 指向树根

  1. cur 无左树,cur = cur.right
  2. cur 有左树,找到左树最右节点 mostright
    a. mostright 右指针指向 null(第1次)
    mostright.right = cur, cur = cur.left
    b. mostright 右指针指向 cur (第2次)
    mostright.right = null, cur = cur.right
    cur == nil,停

先序遍历:能回自己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
}

94. 二叉树的中序遍历

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
}

145. 二叉树的后序遍历

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)
    }
}
2赞

周一:

/**
 * 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;
    }
}

102


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

	}

}

103


/*
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

	}

}

429


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

}

102. 二叉树的层序遍历

方法一:DFS

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
}

方法二:BFS(queue)

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)
    }
}

429. N 叉树的层序遍历

/**
 * 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
}