二叉树的遍历

以力扣的题为例

题目：给你二叉树的根节点 root ，返回它节点值的前序遍历。

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

一：二叉树的递归遍历

前序递归遍历

/**
 * 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 preorderTraversal = function(root, res = []) {
    //递归法
    if(!root) return res
    res.push(root.val)
    preorderTraversal(root.left, res)
    preorderTraversal(root.right, res)
    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 preorderTraversal = function(root, res = []) {
    //递归法
    if(!root) return res
    inorderTraversal(root.left, res)
    res.push(root.val)
    inorderTraversal(root.right, res)
    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 postorderTraversal = function(root, res = []) {
    //递归
    if(!root) return res
    postorderTraversal(root.left, res)
    postorderTraversal(root.right, res)
    res.push(root.val)
    return res
};

二：二叉树的迭代遍历

前序的迭代遍历

递归的迭代遍历理论上都是可以用栈来模拟的

前序遍历即中左右，需要注意的是，由于栈的数据结构先进后出，所以入栈顺序应为右左

//前序遍历 中左右
var preorderTraversal = function(root, res = []) {
    //栈
    //迭代法
    if(!root) return res
    const stack = []
    stack.push(root)
    let node = null
    while(stack.length){
        node = stack.pop()
        res.push(node.val)
        //向将右子节点入栈 再将左子节点入栈
        if(node.right) stack.push(node.right)
        if(node.left) stack.push(node.left)
    }
    return res
};

后序的迭代遍历

后序的迭代遍历和前序很类似

访问的节点都是为当前需要处理的节点

只需要将前序的入栈顺序颠倒一下，最后将数组反转一下即可

var postorderTraversal = function(root, res = []) {
    //迭代
    if(!root) return res
    const stack = []
    stack.push(root)
    let node = null
    while(stack.length){
        node = stack.pop()
        res.push(node.val)
        if(node.left) stack.push(node.left)
        if(node.right) stack.push(node.right)
    }
    return res.reverse()
};

中序的迭代遍历

中序遍历的迭代遍历跟前序后序的迭代遍历有所不同

由于中序的访问节点和当前要处理的节点不是一个节点，所以需要用指针来进行处理

中序 – 左中右

入栈顺序 — 左右

出栈顺序 — 左中右

即先遍历左子节点，访问到的左子节点加入栈中

若子节点为空，弹出栈顶元素

若右子节点为空，弹出栈顶元素

var inorderTraversal = function(root, res = []) {

    // 迭代
    //入栈的 左 -> 右
    //出栈 左 -> 中 -> 右
    if(!root) return res
    const stack = []
    let cur = root
    while(cur || stack.length){
        //向左边遍历 入栈
        if(cur){
            stack.push(cur)
            cur = cur.left
        }else{
            //左 中
            //弹出
            cur = stack.pop()
            //加入数组
            res.push(cur.val)
            //右
            cur = cur.right
        }
    }
    return res
};

三：二叉树的层序遍历

层序遍历，即每层输出元素。

利用队列去实现，类似于广度优先搜索。

将每层的元素放入队列中，同时记录下每层元素的个数

出队的同时，判断是否有子节点，如果有将其入队

这个时候就会遇到例如第二层第三层元素在同一队列，那么当时记录下的元素个数size就起作用了

每次出队的同时，size–，来控制将队列中的该层元素对应出队成功

var levelOrder = function(root) {
    //层序遍历 利用队列去实现 类似与广度优先搜索一样
    let queue = []
    //用于存放最终的二位数组
    let res = []
    //如果根节点为空返回空数组
    if(!root) return res
    //把根节点放入队列中
    queue.push(root)
    //循环终止条件为队列为0
    while(queue.length !== 0){
        //记录下每层的元素个数 
        let length = queue.length
        //用于存放每层元素的一维数组
        let curLevel = []
        for(let i = 0; i < length; i++){
            //弹出队列中的第一个元素 并将其加入到curlevel中
            let node = queue.shift()
            curLevel.push(node.val)
            //判断是否存在左右子节点
            if(node.left) queue.push(node.left)
            if(node.right) queue.push(node.right)
        }
        //将每层curlevel加入到最终数组中
        res.push(curLevel)
    }
    return res

};