白话递归：由二叉树力扣题总结出来的递归思想-一一网

前言

最近在刷力扣中二叉树相关题目，发现很多问题都需要用递归来解决，或者说很多问题用递归来解决会比较简单。但是自己不能够很熟练地运用递归算法，对于递归过程中循环调用递归函数这个思路往往容易陷进去跳不出来。

后来看了一位算法大佬的想法：关于递归的实现逻辑，不用陷入递归的循环中去思考这个递归展开后是什么样，只需要确定我这个递归要实现什么，以及在哪一步实现即可。

总结一下就是：

1.先赋予这个函数一个明确的意义（即我写这个递归函数的目的是什么）
2.写出边界条件
3.最后实现递归过程即可（不用管这个递归过程是怎么执行的）

也就是我们不用思考递归过程是怎么执行的，只需要知道我的这个递归程序对不对，能不能满足我想要的结果

下一节我会结合这段时间刷的一些二叉树相关题目来对这个规律进行代码上的实现

刷题

这一节就开始刷题了，我主要会根据我在力扣上刷的二叉树相关的题目结合递归算法来进行总结。每一题我都会按照递归规律来总结，有不对的地方或者有更好的思路，欢迎大家评论指出~

(‘思路’部分有时我只会写出简单思路，详细步骤会写在代码每一行的注释中，请配合代码食用^-^如果还有不明白的地方，也欢迎在评论区留言讨论）

1.二叉树前序遍历：力扣144题。

思路：简单的递归即可

二叉树的前序、中序、后序遍历其实就是遍历二叉树时根节点的位置问题（根左右、左根右、左右根），本文不再赘述。

话不多说，直接上代码

/**
 * 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[]}
 */
let recursive = (root, arr) => {    // 递归函数--为了实现二叉树的前序遍历
    if (root === null) return    // 边界条件
    arr.push(root.val)           // 前序遍历，所以先把根节点放进数组
    recursive(root.left, arr)    // 再把左节点放进数组
    recursive(root.right, arr)   // 再把右节点放进数组
    return
}
var preorderTraversal = function(root) {
    let res_arr = []    // 声明一个数组来存放遍历结果
    recursive(root, res_arr)
    return res_arr
};
复制代码

2.N叉树的前序遍历：力扣589题。

思路：同二叉树前序遍历一样，定义一个数组存放遍历结果，在递归函数里先塞入根节点的val，然后依次塞入子节点的val即可

上代码

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

/**
 * @param {Node} root
 * @return {number[]}
 */

let recursive = function(root, arr) {    // 递归函数--前序遍历
    if (!root) return        // 边界条件
    arr.push(root.val)       // 塞入根节点
    for (let i = 0; i < root.children.length; i++) {
        recursive(root.children[i], arr)    // 塞入子节点
    }
    return
}
var preorder = function(root) {
    let res_arr = []
    recursive(root, res_arr)
    return res_arr
};
复制代码

3.翻转二叉树：力扣226题。

思路：题目的意思是把一颗二叉树下所有的左右子树进行交换。那么思路也就很清晰了——遍历二叉树，左右节点交换即可

/**
 * 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 null;    // 边界条件
    // 左右子树交换位置，用到了ES6的交换变量方法
    [root.left, root.right] = [root.right, root.left]
    invertTree(root.left)        // 遍历左子树
    invertTree(root.right)       // 遍历右子树
    return root
};
复制代码

4.从上到下打印二叉树：力扣剑指offer32-II题。

思路：定义一个k来记录遍历到的二叉树层数。按照题目要求同样定义一个二维数组来存放遍历结果

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
 
// k用来标记是哪一层，同时代表二维数组arr的下标
let recursive = (root, arr, k) => {    // 递归函数--从上往下遍历二叉树
    if (!root) return        // 边界条件
    if (arr.length == k) arr.push([])    // 说明此时遍历到了新的一层，则在arr中加一层
    arr[k].push(root.val)        // 将此节点的val添加到arr中相应的一层去
    recursive(root.left, arr, k + 1)        // 遍历左子树，层数 + 1
    recursive(root.right, arr, k + 1)       // 遍历右子树，层数 + 1
    return
}

var levelOrder = function(root) {
    let res_arr = []
    recursive(root, res_arr, 0)    // 传入初始值
    return res_arr
};
复制代码

5.二叉树的层序遍历II：力扣107题。

思路：同上一题一样，只不过顺序是从低向上遍历。在上一题的基础上把结果翻转即可，不再做详细注释

let recursive = (root, k, arr) => {
    if (!root) return
    if (arr.length == k) arr.push([])
    arr[k].push(root.val)
    recursive(root.left, k + 1, arr)
    recursive(root.right, k + 1, arr)
    return
}

var levelOrderBottom = function(root) {
    let res_arr = []
    recursive(root, 0, res_arr)
    return res_arr.reverse()    // 将结果翻转即可
};
复制代码

6.二叉树的锯齿形层序遍历：力扣103题。

思路：按照题目要求，这一题的思路和层序遍历一样，在偶数层翻转即可

let recursive = (root, k, arr) => {
    if (!root) return;
    if (k === arr.length) arr.push([])
    arr[k].push(root.val)
    recursive(root.left, k + 1, arr)
    recursive(root.right, k + 1, arr)
}
var zigzagLevelOrder = function(root) {
    let res_arr = []
    recursive(root, 0, res_arr)
    // 其余代码同前两题，在这一步遍历res_arr，对偶数层里的值进行翻转即可
    res_arr.map((item, index) => {
        if((index + 1) % 2 === 0 && item.length > 1) {
            item = item.reverse()
        }
    })
    return res_arr
};
复制代码