美文网首页
代码随想录训练营Day14 | 二叉树遍历

代码随想录训练营Day14 | 二叉树遍历

作者: 是小张啊啊 | 来源:发表于2023-10-24 09:41 被阅读0次
二叉树的遍历方式
  1. 深度优先遍历
  • 前序遍历:根、左、右(递归法、迭代法)
  • 中序遍历:左、根、右(递归法、迭代法)
  • 后序遍历:左、右、根(递归法、迭代法)
举例: image.png

前序遍历:5、4、1、2、6、7、8
中序遍历:1、4、2、5、7、6、8
后序遍历:1、2、4、7、8、6、5

  1. 广度优先遍历
  • 层次遍历(迭代法)
二叉树的存储方式

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

  • 链式存储:利用指针,通过指针把分布在各个地址的节点串联起来
  • 顺序存储:利用数组,存储的元素在内存是连续分布的
    用上图二叉树举例说明一下顺序存储
    如果父节点的数组下标是,那么左节点的数组下标是 i * 2+1,右节点的数组下标是 i * 2+2。
    image.png
144. 二叉树的前序遍历
递归实现
var preorderTraversal = function(root) {
    let res = [];
    var traversal = function(cur) {
      if (cur === null) {
        return
      }
      res.push(cur.val)
      traversal(cur.left)
      traversal(cur.right)
    }
    traversal(root)
    return res;
};
迭代实现
  • 由于前序遍历是先根,后左右节点。所以优先存储根节点,再依次存储右节点、左节点,将左节点放在后面,这样在弹出节点时的顺序才会是先左节点,再右节点。
var preorderTraversal = function(root) {
    if (!root) return []
    let res = [];
    let stack = [];
    stack.push(root)
    while(stack.length) {
        let cur = stack.pop()
        res.push(cur.val)
        if (cur.right) {
            stack.push(cur.right)
        }
        if (cur.left) {
            stack.push(cur.left)
        }
    }
    return res;
};
94. 二叉树的中序遍历
递归实现
var inorderTraversal = function(root) {
    let res = [];
    var traversal = function(root) {
        if (root === null) {
            return
        }
        traversal(root.left);
        res.push(root.val)
        traversal(root.right);
    }
    traversal(root)
    return res;
};
迭代实现
  • 与前序遍历不同,中序遍历需要优先拿到左节点。
  • 先访问的是二叉树顶部的节点,然后一层一层向下访问,直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进结果数组中)。
var inorderTraversal = function(root) {
    let res = [];
    // 迭代遍历 左中右
    let cur = root;
    let stack = [];
    while (cur !== null || stack.length) {
        if (cur !== null) {
            stack.push(cur)
            cur = cur.left
        } else {
            cur = stack.pop()
            res.push(cur.val)
            cur = cur.right
        }
    }
    return res;
};
145. 二叉树的后序遍历
递归实现
var postorderTraversal = function(root) {
    let res = [];
    var traversal = function(root) {
        if (root === null) {
            return
        }
        traversal(root.left);
        traversal(root.right);
        res.push(root.val)
    }
    traversal(root)
    return res;
};
迭代实现
  • 与前序遍历相似,可以转换遍历顺序为根、右、左,再将其结果返回即可。
var postorderTraversal = function(root) {
    if (!root) return []
    let res = [];
    let stack = [];
    stack.push(root)
    while(stack.length) {
        let cur = stack.pop()
        res.push(cur.val)
        if (cur.left) {
            stack.push(cur.left)
        }
        if (cur.right) {
            stack.push(cur.right)
        }
    }
    return res.reverse();
};

相关文章

  • 二叉树的遍历

    二叉树深度遍历的代码 二叉树的遍历代码,遵循一个基本的代码框架。区别在于访问节点数据在什么时候。 二叉树的中序遍历...

  • 二叉树遍历

    二叉树 二叉树的存储结构 前序遍历 中序遍历 后序遍历 遍历代码 反转二叉树 深入学习二叉树 二叉树-你必须要懂!...

  • 【Python】python简单二叉树遍历代码

    标签: <无> [python简单二叉树遍历代码代码][Python]代码

  • 二叉树

    结构体 创建二叉树 递归遍历 栈操作 非递归遍历 层次遍历 完整代码

  • 深入浅出二叉树遍历的非递归算法 2019-11-15(未经允许,

    1、二叉树遍历的递归算法 递归实现二叉树的遍历非常直观,回顾一下递归的代码: 前序遍历 中序遍历 后序遍历 他们的...

  • 2020-05-25 【翻转二叉树】

    翻转一棵二叉树。 解答 递归 后序遍历 代码: 递归 前序遍历

  • 二叉树的递归遍历(java版)

    1. 场景需求 二叉树如图 java中利用递归实现二叉树的各种遍历 前序遍历 中序遍历 后序遍历 3.代码实现 3...

  • 二叉树

    1.二叉树的遍历:前序、中序、后序遍历 2.二叉树查找节点和删除节点的代码

  • 用js实现二叉树的遍历

    二叉树的常用遍历为前序遍历,中序遍历,后序遍历,三种遍历方法仅仅是交换了代码的运行顺序而已,代码如下: 一开始的时...

  • Java二叉树的遍历

    定义二叉树的节点类型 遍历 上述代码分别实现了二叉树的 - **层次优先、前序(先序)、中序、后序 - **遍历,...

网友评论

      本文标题:代码随想录训练营Day14 | 二叉树遍历

      本文链接:https://www.haomeiwen.com/subject/ekrjidtx.html