【Leetcode 做题学算法周刊】第五期

首发于微信公众号《前端成长记》，写于 2019.12.06

背景

本文记录刷题过程中的整个思考过程，以供参考。主要内容涵盖：

• 题目分析设想
• 编写代码验证
• 查阅他人解法
• 思考总结

目录

• 100.相同的树
• 101.对称二叉树
• 104.二叉树的最大深度
• 107.二叉树的层次遍历II
• 108.将有序数组转换为二叉搜索树

Easy

100.相同的树

题目地址

题目描述

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例：

输入:       1         1
          /        / 
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true

输入:      1          1
          /           
         2             2

        [1,2],     [1,null,2]

输出: false

输入:       1         1
          /        / 
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

题目分析设想

题目直接说了是二叉树，而二叉树的遍历方式有两种：深度优先和广度优先，我就从这两个思路来作答。

编写代码验证

Ⅰ.深度优先

代码：

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if (p === null && q === null) return true
    if (p === null || q === null) return false

    if (p.val !== q.val) return false

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};

结果：

• 57/57 cases passed (52 ms)
• Your runtime beats 98.81 % of javascript submissions
• Your memory usage beats 16.66 % of javascript submissions (33.8 MB)
• 时间复杂度 O(n) ，n 为节点个数

Ⅱ.广度优先

代码：

/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    if (p === null && q === null) return true
    if (p === null || q === null) return false

    let pQ =[p] // 左侧比较队列
    let qQ =[q] // 右侧比较队列

    let res = true

    while(true) {
        if (!pQ.length || !qQ.length) {
            res = pQ.length === qQ.length
            break
        }
        // 当前比较节点
        let curP = pQ.shift()
        let curQ = qQ.shift()
        if ((curP && !curQ) || (!curP && curQ) || (curP && curQ && curP.val !== curQ.val)) {
            res = false
            break
        } else {
            let pL = curP ? curP.left : null
            let pR = curP ? curP.right : null
            if (pL || pR) { // 至少一个存在才有意义
                pQ.push(pL, pR) // 依次推入比较数组，实际上就是广度优先
            }
            let qL = curQ ? curQ.left : null
            let qR = curQ ? curQ.right : null
            if (qL || qR) { // 至少一个存在才有意义
                qQ.push(qL, qR) // 依次推入比较数组，实际上就是广度优先
            }
        }
    }

    return res
};

结果：

• 57/57 cases passed (64 ms)
• Your runtime beats 73.27 % of javascript submissions
• Your memory usage beats 15.53 % of javascript submissions (33.8 MB)
• 时间复杂度 O(n) ，n 为节点个数

查阅他人解法

思路基本上都是这两种，未发现方向不同的解法。

思考总结

一般碰到二叉树的题，要么就深度遍历，要么就广度遍历。深度优先，也叫先序遍历。

101.对称二叉树

题目地址

题目描述

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

示例：

    1
   / 
  2   2
 /  / 
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

   1
   / 
  2   2
      
   3    3

说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

题目分析设想

还是一道二叉树的题，所以常规思路就是遍历操作，深度优先或广度优先都可。镜像对称可以观察到很明显的特点是有相同的根节点值，且每个树的右子树与另一个树的左字数对称相等。深度优先的方式，其实就是递归的思路，符合题目的说明。

编写代码验证

Ⅰ.深度优先

代码：

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    function isMirror (l, r) {
        if (l === null && r === null) return true
        if (l === null || r === null) return false

        return l.val === r.val && isMirror(l.left, r.right) && isMirror(l.right, r.left)
    }
    return isMirror(root, root)
};

结果：

• 195/195 cases passed (68 ms)
• Your runtime beats 87.74 % of javascript submissions
• Your memory usage beats 41.48 % of javascript submissions (35.5 MB)
• 时间复杂度 O(n) ，n 为节点个数

Ⅱ.广度优先

代码：

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (root === null) return true
    // 初始队列
    let q = [root.left, root.right]
    // 依次将同级push进队列，每次取两个对称节点进行判断
    while(q.length) {
        let l = q.shift()
        let r = q.shift()
        if (l === null && r === null) continue
        if (l === null || r === null) return false
        if (l.val !== r.val) return false

        q.push(l.left, r.right, l.right, r.left)
    }
    return true
};

结果：

• 195/195 cases passed (64 ms)
• Your runtime beats 94.88 % of javascript submissions
• Your memory usage beats 28.3 % of javascript submissions (35.6 MB)
• 时间复杂度 O(n) ，n 为节点个数

查阅他人解法

看到一个有意思的思路，将树按照左中右的顺序输入到数组，加上层数，该数组也是对称的。

Ⅰ.左中右顺序输出数组

代码：

/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (root === null) return true
    // 输出数组
    let arr = []
    search(arr, root, 1);
    // 入参分别为输出，节点和层级
    function search(output, n, k) {
        if (n.left !== null) {
            search(output, n.left, k+1)
        }

        if (n.right !== null) {
            search(output, n.right, k + 1);
        }
    }
     //判断是否对称
     let i = 0, j = arr.length - 1
     while (i < j) {
         if (arr[i] != arr[j]) {
             return false
         }
         i++
         j--
     }
     return true
};

结果：

• 195/195 cases passed (72 ms)
• Your runtime beats 76.3 % of javascript submissions
• Your memory usage beats 6.11 % of javascript submissions (36.3 MB)
• 时间复杂度 O(n) ，n 为节点个数

思考总结

这道题的大致解法都是遍历节点或者利用队列，只是在递归的细节上会有些差异。左中右输出数组的思路很清奇，虽然效率明显会更低下，但是不失为一种思路。

104.二叉树的最大深度

题目地址

题目描述

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

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

说明: 叶子节点是指没有子节点的节点。

示例：

给定二叉树 [3,9,20,null,null,15,7]，

    3
   / 
  9  20
    /  
   15   7

返回它的最大深度 3 。

题目分析设想

这道题最基本的思路就是计算出每条子节点的深度，再进行比较。为了提升效率，可以增加同级比对，去除不可能是最长节点的叶节点计算。

所以这里我就用以下几种思路来实现深度优先算法。

• 递归，直接获取子树最大高度加 1
• 利用队列，求深度转化为求有多少层

编写代码验证

Ⅰ.递归

代码：

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (root === null) return 0
    // 左侧子树的最大高度
    let l = maxDepth(root.left)
    // 右侧子树的最大高度
    let r = maxDepth(root.right)
    return Math.max(l, r) + 1
};

结果：

• 39/39 cases passed (60 ms)
• Your runtime beats 99 % of javascript submissions
• Your memory usage beats 45.77 % of javascript submissions (37.1 MB)
• 时间复杂度 O(n) ，n 为节点个数

Ⅱ.利用队列

代码：

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (root === null) return 0
    // 队列
    let q = [root]
    let dep = 0
    while(q.length) {
        let size = q.length
        dep++
        while(size > 0) {
            let node = q.shift()
            if (node.left !== null) q.push(node.left)
            if (node.right !== null) q.push(node.right)
            size--
        }
    }
    return dep
};

结果：

• 39/39 cases passed (68 ms)
• Your runtime beats 91.33 % of javascript submissions
• Your memory usage beats 30.1 % of javascript submissions (37.2 MB)
• 时间复杂度 O(n) ，n 为节点个数

查阅他人解法

这里看到一个用栈的角度来实现的，取栈高度的最大值，其他的基本都是循环的细节差异，大体思路一致。

Ⅰ.利用栈

代码：

/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {
    if (root === null) return 0
    // 栈
    let s = [{
        node: root,
        dep: 1
    }]
    let dep = 0

    while(s.length) {
        // 先进后出
        var cur = s.pop()
        if (cur.node !== null) {
            let curDep = cur.dep
            dep = Math.max(dep, curDep)
            if (cur.node.left !== null) s.push({node: cur.node.left, dep: curDep + 1})
            if (cur.node.right !== null) s.push({node: cur.node.right, dep: curDep + 1})
        }
    }
    return dep
};

结果：

• 39/39 cases passed (72 ms)
• Your runtime beats 81.41 % of javascript submissions
• Your memory usage beats 66.6 % of javascript submissions (37 MB)
• 时间复杂度 O(n) ，n 为节点个数

思考总结

二叉树的操作，一般就是深度优先和广度优先，所以基本上就朝这两个方向上去解，然后进行优化就可以了。

107.二叉树的层次遍历II

题目地址

题目描述

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：

给定二叉树 [3,9,20,null,null,15,7],

    3
   / 
  9  20
    /  
   15   7

返回其自底向上的层次遍历为：

[
  [15,7],
  [9,20],
  [3]
]

题目分析设想

这道题在我看来还是两种方式，深度优先和广度优先。

• 深度优先，记录下每个节点对应的层数后，按层数反向输出即可
• 广度优先，记录下每层的节点后反向输出

编写代码验证

Ⅰ.深度优先

代码：

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    // 当前层级标识
    let idx = 0
    let res = []

    function levelOrder(node, floor, arr) {
        if (node === null) return arr
        if(arr[floor]) {
            arr[floor].push(node.val)
        } else {
            arr[floor] = [node.val]
        }
        levelOrder(node.left, floor + 1, arr)
        levelOrder(node.right, floor + 1, arr)
        return arr
    }

    return levelOrder(root, idx, res).reverse()
};

结果：

• 34/34 cases passed (68 ms)
• Your runtime beats 77.01 % of javascript submissions
• Your memory usage beats 34.78 % of javascript submissions (34.7 MB)
• 时间复杂度 O(n) ，n 为节点个数

Ⅱ.广度优先

代码：

/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    if (root === null) return []
    // 初始队列
    let q = [root]
    let res = []

    while(q.length) {
        // 当前层节点数量
        const count = q.length
        let curArr = []
        for(let i = 0; i < count;i++) {
            const node = q.shift()
            curArr.push(node.val)
            // 将子节点依次推入队列
            if (node.left) q.push(node.left)
            if (node.right ) q.push(node.right )
        }
        res.push(curArr)
    }
    return res.reverse()
};

结果：

• 34/34 cases passed (64 ms)
• Your runtime beats 89.2 % of javascript submissions
• Your memory usage beats 32.3 % of javascript submissions (34.7 MB)
• 时间复杂度 O(n) ，n 为节点个数

查阅他人解法

没有看到什么特别的解法，主要都是按 BFS 和 DFS 来处理，要么迭代，要么递归等等。

这里就介绍下别的吧，在第一种解法中我们使用的是前序优先，当然用中序优先或后序优先也可以，下面代码可以说明区别：

// 先序，顺序为 根 -> 左 -> 右
function levelOrder(node, floor, arr) {
    if(arr[floor]) {
        arr[floor].push(node.val)
    } else {
        arr[floor] = [node.val]
    }

    levelOrder(node.left, floor + 1, arr)
    levelOrder(node.right, floor + 1, arr)
    return arr
}
// 中序，顺序为 左 -> 根 -> 右
function levelOrder(node, floor, arr) {
    levelOrder(node.left, floor + 1, arr)

   if(arr[floor]) {
       arr[floor].push(node.val)
   } else {
       arr[floor] = [node.val]
   }

    levelOrder(node.right, floor + 1, arr)
    return arr
}
// 后序，顺序为 左 -> 右 -> 根
function levelOrder(node, floor, arr) {
    levelOrder(node.left, floor + 1, arr)
    levelOrder(node.right, floor + 1, arr)

    if(arr[floor]) {
        arr[floor].push(node.val)
    } else {
        arr[floor] = [node.val]
    }
    return arr
}

思考总结

二叉树的题目就根据情况在深度优先和广度优先中择优选择即可，基本不会有太大的问题。

108.将有序数组转换为二叉搜索树

题目地址

题目描述

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
     / 
   -3   9
   /   /
 -10  5

题目分析设想

这里有两点要注意的：高度平衡二叉树要求每个节点的左右两个子树的高度差的绝对值不超过 1；而二叉搜索树要求左子树上所有节点值小于根节点，右子树上所有节点值大于根节点。

而题目给出的是一个有序的数组，所以可以直接考虑二分后进行处理，我这就直接递归作答：找到根节点，递归生成左右子树。

编写代码验证

Ⅰ.递归

代码：

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    if (!nums.length) return null
    // 中位数，用偏移避免溢出
    const mid = nums.length >>> 1
    const root = new TreeNode(nums[mid])
    root.left = sortedArrayToBST(nums.slice(0, mid))
    root.right = sortedArrayToBST(nums.slice(mid + 1))
    return root
};

结果：

• 32/32 cases passed (80 ms)
• Your runtime beats 70.72 % of javascript submissions
• Your memory usage beats 29.79 % of javascript submissions (37.8 MB)
• 时间复杂度 O(n)

查阅他人解法

这里看到另外一种解法，先创建一个平衡二叉树，然后中序遍历树同时遍历数组即可，因为中序遍历出来的刚好是有序数组。

Ⅰ.创建树后中序遍历数组赋值

代码：

/**
 * @param {number[]} nums
 * @return {TreeNode}
 */
var sortedArrayToBST = function(nums) {
    if (!nums.length) return null

    // 节点总数
    let len = nums.length
    let root = new TreeNode(-1);
    let q = [root]
    // 已经创建了根节点
    len--
    while(len) {
        const node = q.shift()
        // 左子树
        const l = new TreeNode(-1)
        q.push(l)
        node.left = l
        len--
        if (len) {
            // 右子树
            const r = new TreeNode(-1)
            q.push(r)
            node.right = r
            len--
        }
    }

    let i = 0
    inorder(root)
    function inorder(node) {
        if (node === null) return
        inorder(node.left)
        node.val = nums[i++]
        inorder(node.right)
    }

    return root
};

结果：

• 32/32 cases passed (72 ms)
• Your runtime beats 93.4 % of javascript submissions
• Your memory usage beats 24.12 % of javascript submissions (37.8 MB)
• 时间复杂度 O(n)

思考总结

这里其实是个逆向思维，之前是二叉树输出数组，现在变成数组转成二叉树。刚好可以翻一下前序中序和后序的区别，这里中序就可以了。不过这道题我还是更推荐递归二分求解。

（完）

---

本文为原创文章，可能会更新知识点及修正错误，因此转载请保留原出处，方便溯源，避免陈旧错误知识的误导，同时有更好的阅读体验
如果能给您带去些许帮助，欢迎 ⭐️star 或 ✏️ fork
(转载请注明出处：https://chenjiahao.xyz)

• 还没有人评论，欢迎说说您的想法！