【算法之路】? 吃透对称性递归 (二)-一一网

Offer 驾到，掘友接招！我正在参与2022春招系列活动-刷题打卡任务，点击查看活动详情。

前言

数据结构与算法属于开发人员的内功，不管前端技术怎么变，框架怎么更新，版本怎么迭代，它终究是不变的内容。 始终记得在参加字节青训营的时候，月影老师说过的一句话，不要问前端学不学算法。计算机学科的每一位都有必要了解算法，有写出高质量代码的潜意识。

通过本系类的文章带你 穆萨二叉树的对称性问题，废话不多说，直接开始吧！ ?

一、二叉搜索树中第K小的元素

1.1 问题描述

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1
复制代码

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3
复制代码

1.2 题解思路

重点观察本题的要求是二叉搜索树,先简单回顾一下二叉搜索树的一些特点吧。

根节点的左节点小于根节点
根结点的右节点大于根节点

那根据这个要求我们很快就可以想到一个解：通过中序遍历将结果都存放在一个结果集中，结果集一定是从小到大排列，那么我们只需要打印第k个元素就可以了。

1.3 AC代码

var kthSmallest = function(root, k) {
    const res =  []
    const dfs = (root)=>{
        if(!root) return
        dfs(root.left)
        res.push(root.val) // 注意中序遍历
        dfs(root.right)
    }
    dfs(root)
    return res[k-1] // k 从 1开始计数
};
复制代码

进一步优化,那么当res结果集的长度已经够k了是不是可以停止递归了。

var kthSmallest = function(root, k) {
    const res =  []
    const dfs = (root)=>{
        if(!root) return
        if(res.length>=k) return
        dfs(root.left)
        res.push(root.val)
        dfs(root.right)
    }
    dfs(root)
    return res[k-1]
};
复制代码

还能继续优化嘛？上述解法的空间复杂度都是O(N), 既然是需要打印结果集中的第k个元素，为什么我们不直接使用一个count来计数，如果当有效的节点递归次数到底了k，我们直接就返回结果就行了。

var kthSmallest = function(root, k) {
    let count = 0
    let res = 0
    const dfs = (root)=>{
        if(root&&count<=k){
           dfs(root.left)
           if(++count==k){
               res = root.val
           }
           dfs(root.right)
        }
    }
    dfs(root)
    return res
};
复制代码

二、二叉树的层序遍历

2.1 问题描述

给你二叉树的根节点 root ，返回其节点值的层序遍历。（即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
复制代码

示例 2：

输入：root = [1]
输出：[[1]]
复制代码

示例 3：

输入：root = []
输出：[]
复制代码

2.2 题解思路

关于树的层级问题解法都很一致，无论是锯齿状还是一直保存从左往右，我们只需要使用index值来记录即可。

2.3 AC代码

var levelOrder = function(root) {
    const res = []
    const rec = (root,index)=>{
        if(!root) return
        if(!res[index]){
            res[index] = []
        }
        res[index].push(root.val)
        rec(root.left,index+1)
        rec(root.right,index+1)
    }
    rec(root,0)
    return res
};
复制代码

三、二叉树的右视图

3.1 题目描述

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
复制代码

示例 2:

输入: [1,null,3]
输出: [1,3]
复制代码

示例 3:

输入: []
输出: []
复制代码

3.2 题解思路

这道题和上一题很类似，其实就是一个层序遍历问题，这次的层序层级变成了，从右往左计算。而且每一层只计算一次，所以我们的做法也很简单，使用一个数组来记录，看看每一个层级是否已经存在了值，如果存在了就无需存入。

3.3 AC代码

var rightSideView = function(root) {
   const res = []
   const rec = (root,index)=>{
       if(!root) return
       if(!res[index]){
           res.push(root.val)
       }
       rec(root.right,index+1)
       rec(root.left,index+1)
   }
   rec(root,0)
   return res
};
复制代码

四、二叉树的最大深度

4.1 题目描述

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

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

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

示例：

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

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

复制代码

4.2 题解思路

如果上面两个题都做出来了，这个问题就非常简单了，只需要记录层级的最大值即可。

4.3 AC代码

var maxDepth = function(root) {
    let max = 0
    const rec = (root,index)=>{
        if(!root) return
        max = index > max ? index : max  // 执行速度快于 Math.max()
        rec(root.left,index+1)
        rec(root.right,index+1)
    }
    rec(root,1)
    return max
}
复制代码