vlambda博客
学习文章列表

前言

相信大家在面试大厂的过程中都或多或少会遇到一些数据结构与算法的手写题，虽然我们平常工作中可能对这些内容运用的比较少，但我们也应该了解一些常见的数据结构与算法，学习其中的思想，这对我们的代码逻辑能力会有很大的提升。

树

DFS与BFS这两种算法一般出现在树或图的算法中，最常见的就是在树中的应用，所以我们有必要先来了解一下什么是树？

❝

树的定义：是一类重要的非线性数据结构，是以分支关系定义的层次结构。每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树

❞

二叉树

二叉树就是在树的基础上加了一点限制：每个节点最多拥有两个字节点，左子树和右子树是有顺序的不能颠倒。

二叉树的遍历

• 「先序遍历：」 先访问根节点，再访问左子节点，最后访问右子节点。所以以上二叉树的先序遍历结果是：（1，2，4，5，8，9，3，6，7，10）
• 「中序遍历：」 先访问左子节点，再访问根节点，最后访问右子节点。所以以上二叉树的中序遍历结果是：（4，2，8，5，9，1，6，3，7，10）
• 「后序遍历：」 先访问左子节点，再访问右子节点，最后访问根节点。所以以上二叉树的后序遍历结果是：（4，8，9，5，2，6，10，7，3，1）

DFS、BFS

「DFS（深度优先遍历）：」 从根节点出发，然后依次向下继续搜索，直到遇到叶子🍃节点才向上回溯，「DFS通常采用的是栈的形式来处理，即后进先出。」

「BFS（广度优先遍历）：」从根节点出发，沿着树的宽度，每次都「访问同一层的节点」，若同一层都访问完，再访问下一层，若所有的节点都被访问，则算法终止，最后BFS找到的路径即为最短路径。「BFS通常采用的是队列的形式来处理，即先进先出。」

看下面这张图理解起来应该会更加清晰

「BFS 和 DFS 是很重要的算法，BFS 的重点在于队列，而 DFS 的重点在于递归；它们在搜素领域有非常大的发挥空间。BFS相对于DFS，DFS是一条路走到底，没有先后顺序，BFS按层级遍历，好记录当前遍历层级，更利于求最优路径。」

高频算法题

1.二叉树的最大深度（104.easy🌟）

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

「示例：」给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度3。（题目来源于leetcode)

DFS解法

「思路：」

• 采用递归遍历左右节点
• 每次递归，深度加1

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root){
        return 0
    }else {
        const left = maxDepth(root.left)
        const right = maxDepth(root.right)
        return Math.max(left, right) + 1
    } 
};

BFS解法

「思路：」

• 维护一个队列，先将根节点推入队列
• 开启一个while循环，然后再遍历该队列，将每一项取出来看是否存在左右子节点，有则推入队列
• 这样while这一层就只控制了二叉树的层数，而里面的for循环则控制了每一层的节点树

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if(!root) return 0
    let res = 0, queue = [root]
    while(queue.length) {
        const len = queue.length
        for(let i=0; i<len; i++) {
             const currentNode = queue.shift()
             if(currentNode.left) queue.push(currentNode.left)
             if(currentNode.right) queue.push(currentNode.right)
        }
        res++
       
    }
    return res
};

2.二叉树的最小深度（111.easy🌟）

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

「示例：」给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回它的最小深度2。（题目来源于leetcode)

DFS解法

「思路：」

• 深度优先遍历，每次递归深度加1，找出最小值

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if(!root) return 0 // 根节点为空就是0
    if(root.left === null && root.right === null) return 1 //无左右子节点就是1
    let res = Number.MAX_SAFE_INTEGER;
    // 递归左右节点
    if(root.left) {
        res = Math.min(res, minDepth(root.left))
    }
    if(root.right) {
        res = Math.min(res, minDepth(root.right))
    }
    return res + 1

};

BFS解法

「思路：」

• 广度优先遍历
• 找到第一个没有左右子节点的层级就是最小深度

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if(!root) return 0
    let queue = [root], res = 1

    while(queue.length) {
        let len = queue.length//
        for(let i=0; i<len; i++) {
            let current = queue.shift()
            if(!current.left && !current.right) {
                return res
            }
            if(current.left) {
                queue.push(current.left)
            }
            if(current.right) {
                queue.push(current.right)
            }
        }
        res++
    }

};

3.二叉树的右视图（199.middle🌟🌟)

给定一个二叉树的 「根节点」 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。（题目来源于leetcode)

「示例：」

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

DFS解法

「思路：」

• 递归遍历二叉树
• 由于是右视图，所以优先遍历根节点再遍历右子节点最后遍历左子节点
• 记录一个层级，当层级与返回值res的length相等，则说明它是当前层级最右边的节点，所以将它push进res

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
    if(!root) return []
    let res = []
    dfs(root, 0)
    function dfs(node, depth) {
        if(res.length === depth) res.push(node.val)
        if(node.right) dfs(node.right, depth+1)
        if(node.left) dfs(node.left, depth+1)

    }
    return res
};

BFS解法

「思路：」

• 采用BFS的关键是push每一层的第一个
• 而保证是右视图的关键是每次先将右子节点push进去（队列先进先出）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var rightSideView = function(root) {
    if(!root) return []
    let queue = [root], res = []
    while(queue.length) {
        let len = queue.length        
        for(let i=0; i<len; i++) {
            let current = queue.shift()
            if(i === 0) res.push(current.val) // i为0说明是该层的第一个
            if(current.right) queue.push(current.right) // 队列先进先出，先将右子节点push进去
            if(current.left) queue.push(current.left)
        }
    } 
    return res
};

4.翻转二叉树（226.easy🌟）

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。（题目来源于leetcode)

「示例 ：」

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

DFS解法

「思路：」

• DFS递归二叉树
• 左右交换位置

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if(!root) return root

    dfs(root)
    function dfs(node) {
        if(node.left===null && node.right===null) return // 递归出口，叶子节点
        [node.left, node.right] = [node.right, node.left] //交换位置
        if(node.left) dfs(node.left)
        if(node.right) dfs(node.right)
    }
    return root
};

BFS解法

「思路：」

• BFS按层级左右交换位置

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    if(!root) return root
    
    let queue = [root]

    while(queue.length) {
        const len = queue.length
        
        for(let i=0; i<len; i++) {
            let current = queue.shift()
            if(!current) return current
             // 翻转左右子节点
            let temp = current.left;
            current.left = current.right;
            current.right = temp;
            if(current.left) queue.push(current.left)
            if(current.right) queue.push(current.right)
        }
    }
    return root
};

5.二叉树的层序遍历（102.middle🌟🌟）

给你二叉树的根节点 root ，返回其节点值的 「层序遍历」 。（即逐层地，从左到右访问所有节点）。（题目来源于leetcode)

「示例 ：」

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

DFS解法

「思路：」

• DFS递归二叉树
• 递归深度对应返回数组层序下标

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root) return []
    let res = []
    dfs(root, 0)
    function dfs(node, depth) {
        if(!res[depth]) {
            res[depth] = [node.val]
        }else {
            res[depth].push(node.val)
        }

        if(node.left) dfs(node.left, depth+1) // 递归深度增加
        if(node.right) dfs(node.right, depth+1) // 递归深度增加
    }
    return res
};

BFS解法

「思路：」

• bfs层序遍历，while即控制的是二叉树的层级
• 关键在于层级与返回值的index对应

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root) return []
    let res = [], queue = [root], depth = 0

    while(queue.length) {
        let len = queue.length
        for(let i=0; i<len; i++) {
            let current = queue.shift()
            // 这里是判断当前层级是否有值，也就是是否是该层的第一个
            if(!res[depth]) {
                res[depth] = [current.val]
            }else{
                res[depth].push(current.val)
            }
            if(current.left) queue.push(current.left)
            if(current.right) queue.push(current.right)
        }
       // 层级增加
        depth++
    }
    
    return res
};

6.N叉树的层序遍历（429.middle🌟🌟）

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。（题目来源于leetcode)

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

「示例：」

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

我们可以看到n叉树与二叉树不同的是他的子节点最多不止两个。

DFS解法

「思路：」

• 其实与二叉树的层序遍历类似
• 不同点在于它没有左右子节点，而是通过遍历子节点children来进行递归

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root) return []
    let res = []
    dfs(root, 0)
    function dfs(node, depth) {
        if(!node.children) return
        if(!res[depth]) {
            res[depth] = [node.val]
        }else {
            res[depth].push(node.val)
        }
        if(node.children) {
            for(let i=0; i<node.children.length; i++) {
                 dfs(node.children[i], depth+1) 
            }   
           
        }
    }
    return res
};

BFS解法

「思路：」

• 与二叉树的层序遍历类似
• 不同点在于它没有左右子节点，而是通过遍历子节点children来推入队列

/**
 * // Definition for a Node.
 * function Node(val,children) {
 *    this.val = val;
 *    this.children = children;
 * };
 */

/**
 * @param {Node|null} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    if(!root) return []
    let res = [],queue = [root], depth = 0

    while(queue.length) {
        let len = queue.length

        for(let i=0; i<len; i++) {
            let current = queue.shift()
            if(!res[depth]) {
                res[depth] = [current.val]
            }else {
                res[depth].push(current.val)
            }

            if(current.children) {
                for(let i=0; i< current.children.length; i++) {
                    queue.push(current.children[i])
                }
            }
        }
        depth++
    }
    
    return res
};

7.二叉树的锯齿形层序遍历（103.middle🌟🌟）

给你二叉树的根节点 root ，返回其节点值的 「锯齿形层序遍历」 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

「示例：」

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

DFS解法

「思路：」

• 这个与二叉树的层序遍历差不多
• 关键是判断当前递归深度，层数从0开始的，奇数往前推进数组，否则往后推进数组

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    if(!root) return []

    let res = []
    dfs(root, 0)

    function dfs(node, depth) {
        if(!node) return
        if(!res[depth]) {
            res[depth] = [node.val]
        }else if(depth%2 != 0) { 
          // 这里是关键，层数从0开始的，奇数往前推进数组，否则往后推进数组
            res[depth].unshift(node.val)
        }else {
            res[depth].push(node.val)
        }

        if(node.left) dfs(node.left, depth+1)
        if(node.right) dfs(node.right, depth+1)

    }
    return res
};

BFS解法

「思路：」

• 与而参数的层序遍历类似
• 关键是判断当前层级的奇偶性，来控制当前是往前推入数组还是往后推入数组

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    if(!root) return []

    let res = [], queue = [root], depth = 0

    while(queue.length) {
        let len = queue.length
        for(let i=0; i<len; i++) {
            let current = queue.shift()
            if(!res[depth]) {
                res[depth] = [current.val]
            }else if(depth%2 !== 0) {
              // 这里是关键
                res[depth].unshift(current.val)
            }else {
                res[depth].push(current.val)
            }
            if(current.left) queue.push(current.left)
            if(current.right) queue.push(current.right)
        }
        depth++
    }
    return res
};

8.二叉树的中序遍历（94.easy🌟）

给定一个二叉树的根节点 root ，返回 它的 「中序」 遍历 。（题目来源于leetcode)

「示例 ：」

输入：root = [1,null,2,3]
输出：[1,3,2]

DFS解法

「思路：」

• 中序遍历 左->根->右

• DFS递归先递归左节点，再递归右节点

• 前序遍历：打印 - 左 - 右

• 中序遍历：左 - 打印 - 右

• 后序遍历：左 - 右 - 打印

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    // 中序遍历 左->根->右
    if(!root) return []

    let res = []
    dfs(root)
    function dfs(node) {
        if(!node) return
        if(node.left) {
            dfs(node.left)
        }
        res.push(node.val)
        if(node.right) {
            dfs(node.right)
        }
    }
    return res
};

迭代解法

「思路：」（这个可能没有上面递归好理解）

• 维护一个栈，先一直迭代左子树入栈，直到左子树为空
• 然后出栈，打印值，再迭代右子树（后进先出）

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    // 中序遍历 左->根->右
    if(!root) return []

    let res = [], stack = []

    while(root || stack.length) {
        while(root) {
            stack.push(root)
            root = root.left
        }
        root = stack.pop()
        res.push(root.val)
        root = root.right
        
    }
    
    return res
};

9.路径总和（112.easy🌟）

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。（题目来源于leetcode)

「示例 ：」

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

DFS解法

「思路：」

• DFS递归左右节点都为null了，说明到了叶子节点，计算完毕将其存入数组
• 判断targetSum是否在数组内

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
    if(!root) return false
    let res = []
    dfs(root, 0)
    function dfs(root, total) {
        total += root.val
        if(root.left===null && root.right === null) {
          // 左右节点都为null了，说明到了叶子节点，计算完毕将其存入数组
            res.push(total)
            return
        }
        if(root.left) dfs(root.left, total)
        if(root.right) dfs(root.right, total)

    }
    return res.includes(targetSum)
};

BFS解法

「思路：」

• bfs每次遍历是累加对应的左右节点的值
• 直到叶子节点并与targetSum比较

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} targetSum
 * @return {boolean}
 */
var hasPathSum = function(root, targetSum) {
    if(!root) return false
    let queue = [root] 

    while(queue.length) {
        let len = queue.length
        for(let i=0; i<len; i++) {
            let current = queue.shift()
            if(current.left === null && current.right === null && current.val === targetSum) {
                return true
            }
            if(current.left) {
                current.left.val += current.val
                queue.push(current.left)
            }
            if(current.right){
                current.right.val += current.val
                queue.push(current.right)
            }
        }
    }
    
    return false
};

10.二叉树最大宽度（662.middle🌟🌟）

给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

每一层的宽度被定义为两个端点（该层最左和最右的非空节点，两端点间的null节点也计入长度）之间的长度。（题目来源于leetcode)

「示例 :」

输入: 
       1
     /   \
    3     2
   / \     \  
  5   3     9 
  
输出: 4
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。

BFS解法

「思路：」

• 与正常BFS思路差不多，只不过这里需要多维护一个节点坐标队列，用于计算每层的宽度
• 需要注意JS数组最大元素个数

看下面这张图会更容易理解一点

这道题的最后几个测试用例很离谱，超出了JS数组的最大元素个数Math.pow(2, 32) - 1，所以需要特殊处理一下

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var widthOfBinaryTree = function(root) {
    if(!root) return 0
  // 维护两个队列， queue节点队列，indexQ节点对应下标队列
    let res = 0, queue = [root], indexQ = [1], width=0 

    while(queue.length) {
       // 层
        let length = queue.length, initIndex = indexQ[0], index = initIndex
        for(let i=0; i<length; i++) {
            //遍历当前层的所有节点
            let current = queue.shift() // 当前节点
            index = indexQ.shift() //当前节点对应的下标
            let can = Math.pow(2, 32) - 1 ; // 数组最大元素个数
            if(current.left !== null) {
                queue.push(current.left)
                indexQ.push(index*2 %can)
            }
            if(current.right !== null) {
                queue.push(current.right)
                indexQ.push((index*2 + 1) % can)
            }
        }
        width = index - initIndex +1
        res = Math.max(res, width)
        
    }
    return res
};

总结

这么做下来，其实解法都是大同小异，所以自己一定需要理解这两种算法与二叉树的特点，可以多去系统的做一做，后面的该系列题目解法会在github上更新。

精彩推荐

END

欢迎关注【前端南玖】，回复进群，拉你进前端交流群一起学习，回复资料，获取前端书籍📚以及学习视频

点分享、在看让更多的人看到这篇文章，你的支持是我持续创作的动力

点个在看你最好看