代码随想录算法训练营第13天｜二叉树Part01

本文主要介绍了二叉树的存储和遍历方法。

二叉树储存方法

二叉树可以链式存储，也可以顺序存储。

二叉树遍历方法

1.深度优先遍历 DFS

• 前序遍历（递归法，迭代法）
• 中序遍历（递归法，迭代法）
• 后序遍历（递归法，迭代法）

2.广度优先遍历 BFS

• 层次遍历（迭代法）

• 前序遍历

• 中序遍历

• 后序遍历

• 层序遍历

var preorderTraversal = function(root) {
  return root
    ? [root.val, ...preorderTraversal(root.left), 
    ...preorderTraversal(root.right)] : [];
};

var preorderTraversal = function(root, res = []) {
    const stack = [];
    if (root) stack.push(root);
    while(stack.length) {
        const node = stack.pop();
        if(!node) {
            res.push(stack.pop().val);
            continue;
        }
        if (node.right) stack.push(node.right);
        if (node.left) stack.push(node.left);
        stack.push(node);
        stack.push(null);
    };
    return res;
};

var inorderTraversal = function(root) {
  return root
    ? [...inorderTraversal(root.left), 
    root.val, ...inorderTraversal(root.right)] : [];
};

var inorderTraversal = function(root, res = []) {
    const stack = [];
    if (root) stack.push(root);
    while(stack.length) {
        const node = stack.pop();
        if(!node) {
            res.push(stack.pop().val);
            continue;
        }
        if (node.right) stack.push(node.right);
        stack.push(node);
        stack.push(null);
        if (node.left) stack.push(node.left);
    };
    return res;
};

var postorderTraversal = function(root) {
  return root
    ? [...postorderTraversal(root.left), 
    ...postorderTraversal(root.right), root.val] : [];
};

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

var levelOrder = function(root) {
    //二叉树的层序遍历
    let res = [], queue = [];
    queue.push(root);
    if(root === null) {
        return res;
    }
    while(queue.length !== 0) {
        // 记录当前层级节点数
        let length = queue.length;
        //存放每一层的节点
        let curLevel = [];
        for(let i = 0;i < length; i++) {
            let node = queue.shift();
            curLevel.push(node.val);
            // 存放当前层下一层的节点
            node.left && queue.push(node.left);
            node.right && queue.push(node.right);
        }
        //把每一层的结果放到结果数组
        res.push(curLevel);
    }
    return res;
};

常见用途

遍历类型	常见用途
前序遍历 DFS	构造路径、序列化树、翻转、复制树等
中序遍历 DFS	二叉搜索树（BST）相关操作，如验证、有序性恢复等
后序遍历 DFS	删除树、计算深度、后置汇总型操作等
层序遍历 BFS	按层输出、最短路径、分层汇总、节点可见性等问题

特性对比

对比维度	深度优先遍历（DFS）	广度优先遍历（BFS）
遍历顺序控制	顺序灵活：可先左后右， 也可先右后左	顺序固定： 逐层从左到右，从上到下
实现方式	递归（利用系统调用栈） 或显式使用栈模拟	显式使用队列迭代实现
路径构造	可通过递归参数或栈自动记录 路径，天然支持根到叶路径	需显式记录路径（通常需 额外数组或字符串同步）
信息传递能力	子调用可通过参数或返回值传递 信息，便于处理父子关联逻辑	当前仅处理一个节点， 无法感知同层其他节点信息
适合的题型	结构型问题：如树高计算、 路径和、镜像翻转、构造路径、 子结构判断等	层级型问题：如每层最大值、 最短路径、层序遍历、 右视图等
可否中途返回	支持灵活剪枝（如：找到 目标路径即返回）	可中途 break， 但路径信息管理较复杂
显式结构需求	递归时依赖调用栈即可 迭代需手动维护栈结构	必须使用显式队列 维护节点状态