章节主要目的

看题目就应该知道是算法题的思路，这里不理解为完全为了面试，这样会很累的，权当做技术的追求吧，我们除了增删改查，复制粘贴，写服务，封装代码，总要找点有其他动脑子的事情做吧，虽说全局观很重要，架构很重要，但是我们总要给自己找个学习的理由吧😄

回到正题，我们写需求之前都会写个概要设计文档（当然现在很多人已经没有这习惯，公司也没有这要求了，但是不妨碍我们的习惯）。算法也是一样，知道远离和实现方式，剩下写代码似乎也并不是很轻松的一件事，因为要涵盖很多种情况，有时候仅仅是一个条件判断条件写错了，就会让你找好久。但是一切的前提就是，你得知道怎么实现，通用情况下怎么实现的，然后才能完善其他的测试用例。

本章节主要介绍的是两方面：1、抽象问题形象化 2、复杂问题简单化。理论永远是简单的，实践才是难题。这一张我看的本身就很累，前面已经说过了，时间会比较久。后面三章时间会更久，因为目前为止还没有涉及到困难级别的题，默哀吧，骚年。

正式开始第四章

面试题19：二叉树的镜像

leetcode-cn.com/problems/er-cha-sh...

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

显然，优先使用前序遍历，首先要学会前序遍历一棵树

func mirrorTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    root.Right, root.Left = root.Left, root.Right
    if root.Left != nil {
        mirrorTree(root.Left)
    }
    if root.Right != nil {
        mirrorTree(root.Right)
    }
    return root
}

这题明显就是让我们找快感的题左右互换而已。

面试题20：顺时针打印矩阵

leetcode-cn.com/problems/shun-shi-...

func spiralOrder(matrix [][]int) []int {
    result := make([]int, 0)
    if matrix == nil || len(matrix) == 0 {
        return nil
    }
    var row = len(matrix)
    var col = len(matrix[0])
    if row <= 0 || col <= 0 { //一行或者一列，直接返回遍历之后的一维数组   
        for i := 0; i < row; i++ {
            for j := 0; j < col; j++ {
                result = append(result, matrix[i][j])
            }
        }
        return result
    }
    startIndex := 0 //起始添加的位置   
    for col > startIndex*2 && row > startIndex*2 {
        endX := col - startIndex - 1
        endY := row - startIndex - 1

        //从左到右添加   
        for i := startIndex; i <= endX; i++ {
            result = append(result, matrix[startIndex][i])
        }
        //从上到下添加   
        if startIndex < endY {
            for i := startIndex + 1; i <= endY; i++ {
                result = append(result, matrix[i][endX])
            }
        }
        //从右到左添加   
        if startIndex < endX && startIndex < endY {
            for i := endX - 1; i >= startIndex; i-- {
                result = append(result, matrix[endY][i])
            }
        }
        //从下到上添加   
        if startIndex < endX && startIndex < endY-1 {
            for i := endY - 1; i >= startIndex+1; i-- {
                result = append(result, matrix[i][startIndex])
            }
        }
        startIndex++
    }

    return result
}

不要小瞧这道题，看原理我们都知道怎么实现，但是写代码的难度比理解远离更困难，重点是，力扣认为这是一道简单题。用网友的话说，这怕不是对简单两个字有什么误解。。。

面试题21：包含min函数的栈

leetcode-cn.com/problems/bao-han-m...

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

这是一道设计题，考察的完全是栈和辅助栈的用法，我觉得没必要去看，本着面试写代码的原则，写了本地也没法测试，只能交给leetcode。

面试题22：栈的压入、弹出序列

leetcode-cn.com/problems/zhan-de-y...

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。

假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

func validateStackSequences(pushed []int, popped []int) bool {
    //1、数组模拟栈   
    //indexPopped := 0   
    //tempPushed := make([]int, 0)   
    //for i := 0; i < len(pushed); i++ {   
    //    tempPushed = append(tempPushed, pushed[i])   
    //    for len(tempPushed)>0 && tempPushed[len(tempPushed)-1] == popped[indexPopped] { //比较栈顶值是否等于popped的当前值   
    //        tempPushed = tempPushed[:len(tempPushed)-1]   
    //        indexPopped++   
    //    }   
    //}   
    //if len(tempPushed) == 0 {   
    //    return true   
    //}   
    //return false   
    //2、栈实现
    indexPopped := 0
    stack := NewStack()
    for i := 0; i < len(pushed); i++ {
        stack.Push(pushed[i])
        for !stack.IsEmpty() && stack.Peek() == popped[indexPopped] { //比较栈顶值是否等于popped的当前值
            stack.Pop()
            indexPopped++
        }
    }
    return stack.IsEmpty()
}

面试题23：从上到下打印二叉树

leetcode-cn.com/problems/cong-shan...

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

func levelOrder(root *TreeNode) []int {
    // 数组模拟队列
    result := make([]int, 0)
    if root == nil {
        return result
    }
    //层次遍历，想明白还是很简单的
    level := make([]*TreeNode, 0) //记录每一层的元素，方便寻找每一层的子节点
    level = append(level, root)   //首先添加第一层   
    for len(level) > 0 { //一层一个数据都没有跳出循环   
        for i := 0; i < len(level); i++ { //遍历当前层，添加子节点层
            result = append(result, level[i].Val)
        }
        temp := level
        for i := 0; i < len(temp); i++ {//模拟双端队列，pushFront数据   
            if temp[i].Left != nil {
                level = append(level, temp[i].Left)
            }
            if temp[i].Right != nil {
                level = append(level, temp[i].Right)
            }
        }
        level = level[len(temp):]//popBack数据
    }
    return result
}

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

升级后只需要区分层级的奇偶就行，逻辑类似

func levelOrder(root *TreeNode) [][]int {
    // 数组模拟队列
    result := make([][]int, 0)
    if root == nil {
        return result
    }
    //层次遍历，想明白还是很简单的
    level := make([]*TreeNode, 0) //记录每一层的元素，方便寻找每一层的子节点
    level = append(level, root)   //首先添加第一层
    high := 0 
    for len(level) > 0 { //一层一个数据都没有跳出循环
        data := make([]int, 0)
        for i := 0; i < len(level); i++ { //遍历第一层，添加子节点层
            data = append(data, level[i].Val)
        }
        temp := level
        high++
        for i := 0; i < len(temp); i++ {
            if temp[i].Left != nil {
                level = append(level, temp[i].Left)
            }
            if temp[i].Right != nil {
                level = append(level, temp[i].Right)
            }
        }
        level = level[len(data):]
        if high%2 == 0 {
            for i := 0; i < len(data)/2; i++ {
                data[i], data[len(data)-1-i] = data[len(data)-1-i], data[i]
            }
        }
        result = append(result, data)
    }
    return result
}

面试题24： 二叉搜索树的后序遍历序列

leetcode-cn.com/problems/er-cha-so...

func verifyPostorder(postorder []int) bool {
    return verifyPostorderCheck(postorder, 0, len(postorder)-1)
}

func verifyPostorderCheck(postorder []int, left, right int) bool {
    if left >= right {
        return true
    }
    leftIndex := left
    for postorder[leftIndex] < postorder[right] {
        leftIndex++
    }
    rightIndex := leftIndex
    for i := rightIndex; i < right; i++ {
        if postorder[i] < postorder[right] {
            return false
        }
    }
    //判断左子树是不是二叉搜索树
    leftResult := verifyPostorderCheck(postorder, left, rightIndex-1)
    //判断右子树是不是二叉搜索树
    rightResult := verifyPostorderCheck(postorder, rightIndex, right-1)
    return leftResult && rightResult
}

面试题25： 二叉树中和为某一值的路径

leetcode-cn.com/problems/er-cha-sh...

典型的回溯 递归大法

func pathSum(root *TreeNode, target int) (result [][]int) {
    cachePath := make([]int, 0)
    var pathSumDfs func(root *TreeNode, sum int)
    pathSumDfs = func(root *TreeNode, sum int) {
        if root == nil {
            return
        }
        sum -= root.Val
        cachePath = append(cachePath, root.Val)
        defer func() { cachePath = cachePath[:len(cachePath)-1] }()
        //判断是不是叶子节点，并且路径值等于目标值   
        if sum == 0 && root.Left == nil && root.Right == nil {
            //result = append(result, cachePath)   
            //需要复制出一个副本，否则就是指针传递了
            result = append(result, append([]int(nil), cachePath...))
            return
        }
        //不是就继续递归子节点
        pathSumDfs(root.Left, sum)
        pathSumDfs(root.Right, sum)
    }
    pathSumDfs(root, target)
    return
}

面试题26：复杂链表的复制

leetcode-cn.com/problems/er-cha-sh...

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，

还有一个 random 指针指向链表中的任意节点或者 null。

random 指针:当前节点的随机指针指向的节点可能还没创建

// 直接两次循环遍历 超出时间限制
func copyRandomList(head *Node) *Node {
    dummy := &Node{}
    tail := dummy
    copyNode := head
    nextNode := head
    for copyNode != nil {
        for nextNode != nil {
            tail.Next = copyNode
            if copyNode.Random == nextNode {
                tail.Random = nextNode
                break
            }
            nextNode = nextNode.Next
        }
    }
    return dummy.Next
}
//回溯+哈希
func copyRandomList(head *Node) *Node {
    var clone func(node *Node) *Node
    cacheNodes := make(map[*Node]*Node)
    clone = func(node *Node) *Node {
        if node == nil {
            return nil
        }
        if n, has := cacheNodes[node]; has {
            return n
        }
        cloneNode := &Node{Val: node.Val}
        cacheNodes[node] = cloneNode
        cloneNode.Next = clone(node.Next)
        cloneNode.Random = clone(node.Random)
        return cloneNode
    }
    return clone(head)
}

分治 迭代 + 节点拆分

func copyRandomList(head *Node) *Node {
    //1、复制自身节点
    cloneNodes := func(head *Node) {
        cloneHead := head
        for cloneHead != nil {
            newNode := &Node{Val: cloneHead.Val, Next: cloneHead.Next}
            cloneHead.Next = newNode
            cloneHead = newNode.Next
        }
    }
    //2、复制随机节点
    cloneRandom := func(head *Node) {
        cloneRandomHead := head
        for cloneRandomHead != nil {
            randomNode := cloneRandomHead.Next
            if cloneRandomHead.Random != nil {
                randomNode.Random = cloneRandomHead.Random.Next
            }
            cloneRandomHead = randomNode.Next
        }
    }
    //3、奇偶拆分链表
    splitNode := func(head *Node) *Node {

        return nil
    }
    cloneNodes(head)
    cloneRandom(head)
    return splitNode(head)
}

面试题27： 二叉搜索树与双向链表

leetcode-cn.com/problems/er-cha-so...

leetcode没有提供Go版本的语言实现这道题，所以只能是仿照编译，本地执行，其他语言自行实现

本题我也没搞懂，看课本答案才知道怎么实现的，惭愧，很多写法不是人家给出Demo我都不知道还可以这么写

type Node struct {
    Val   int
    left  *Node
    right *Node
}

func treeToDoublyList(root *Node) *Node {
    var lastNodeInList *Node //已经转换好的链表的最后一个结点
    convertNode(root, &lastNodeInList)
    headOfList := lastNodeInList //需要返回的头节点   
    for headOfList != nil && headOfList.left != nil {
        headOfList = headOfList.left
    }
    return headOfList
}

func convertNode(root *Node, lastNodeInList **Node) {
    if root == nil {
        return
    }
    currentNode := root
    if currentNode.left != nil {
        convertNode(currentNode.left, lastNodeInList)
    }
    currentNode.left = *lastNodeInList
    if *lastNodeInList != nil {
        (*lastNodeInList).right = currentNode
    }
    *lastNodeInList = currentNode
    if currentNode.right != nil {
        convertNode(currentNode.right, lastNodeInList)
    }
}

面试题28：字符串的排列

leetcode-cn.com/problems/zi-fu-chu...

func permutation(s string) []string {
    result := make([]string, 0)
    byteStr := []byte(s)
    //fmt.Println(byteStr)   
    var getStrDfs func(index int)
    getStrDfs = func(index int) {
        if index == len(byteStr)-1 { //交换到最后一个字符，退出循环   
            //fmt.Println("the end byte", byteStr)
            result = append(result, string(byteStr))
        }
        mapIsChange := make(map[byte]byte) //利用集合做剪枝，去重处理   
        for i := index; i < len(byteStr); i++ {
            if _, ok := mapIsChange[byteStr[i]]; ok {
                continue //已经交换过，不再交换
            }
            mapIsChange[byteStr[i]] = byteStr[i]
            byteStr[i], byteStr[index] = byteStr[index], byteStr[i]//交换
            getStrDfs(index + 1)
            byteStr[i], byteStr[index] = byteStr[index], byteStr[i]//恢复交换
        }
    }

    getStrDfs(0)
    return result
}

小结

总体来说，树的考察比较多，对于树本身就不是常用的搬砖农民工来说，就是个劣势。雪上加霜的是，跟树相关的，必定是递归。我们平时写代码尽量规避递归的代码规范来说，这又是一个挑战。总而言之，这一章确实不容易，建议知道原理的情况下写代码，然后能白板写出来才算真的懂了，否则就是浪费时间，因为不会写代码实现的题，你其实还是不会。