专栏首页前端小书童一天一大 lee(二叉树的中序遍历)难度:中等-Day20200914

一天一大 lee(二叉树的中序遍历)难度:中等-Day20200914

题目:

给定一个二叉树,返回它的中序 遍历。

示例:

输入: [1,null,2,3]
   1
    \
     2
    /
   3

输出: [1,3,2]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

抛砖引玉

抛砖引玉

思路

二叉树的中序遍历:

左子树——>根节点——>右子树

**注意:**这个遍历顺序不仅仅是遍历二叉树整体的顺序也是遍历所有子树的顺序

递归

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  let _result = []
  function helper(node) {
    if (!node) {
      return
    }
    // 先深层遍历左子树
    helper(node.left)
    // 再遍历左子树的根节点
    _result.push(node.val)
    // 最后深层遍历当前根节点的右子树
    helper(node.right)
  }
  helper(root)
  return _result
}

递归方法采用了深度优先遍历的形式,一般可以采用深度优先遍历就可以采用广度优先遍历。

  • 从根节点开始这个查找其左节点(先入后出)
  • 遍历完左节点,逐个取出栈内节点
  • 当前节点不仅仅是单个二叉树节点,也可能是二叉子树,如果其是二叉子树同样遍历其左节点入栈
var inorderTraversal = function(root) {
  let _result = [],
    stack = []
  while (root || stack.length) {
    // 遍历节点左子树,入栈
    while (root) {
      stack.push(root)
      root = root.left
    }
    // 节点(子树)逐个出栈,存放到结果数字
    root = stack.pop()
    _result.push(root.val)
    // 如果出栈的是子树则同第一个有节点开始重复上面的逻辑
    root = root.right
  }
  return _result
}

Morris 中序遍历

20200808: 恢复二叉搜索树 (难度:困难)中,还遇到了Morris 中序遍历的方法

假设当前遍历到的节点为 node:

  • 如果 node 无左孩子,先将 node 的值加入答案数组,再访问 node的右孩子,即 node = node.right
  • 如果 node 有左孩子,则找到 node 左子树上最右的节点(即左子树中序遍历的最后一个节点,node 在中序遍历中的前驱节点),记为predecessor。根据predecessor 的右孩子是否为空,进行如下操作:
    • 如果predecessor 的右孩子为空,则将其右孩子指向 node,然后访问 node 的左孩子,即 node = node.left
    • 如果predecessor 的右孩子不为空,则此时其右孩子指向 node,说明我们已经遍历完 node 的左子树,将predecessor 的右孩子置空,将 node 的值加入答案数组,然后访问 node 的右孩子,即 node = node.right

简要的讲就是,在中序遍历是在左子树走到尽头是,需要回溯到之前出现的某个节点的右节点上,就使用predecessor记录这个回溯的位置,是不存在关系的节点在遍历时连续起来。

var inorderTraversal = function(root) {
  let _result = [],
      predecessor = null

  while (root) {
    if (root.left) {
      // predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止
      predecessor = root.left
      while (predecessor.right && predecessor.right !== root) {
        predecessor = predecessor.right
      }

      // 让 predecessor 的右指针指向 root,继续遍历左子树
      if (!predecessor.right) {
        predecessor.right = root
        root = root.left
      }
      // 说明左子树已经访问完了,我们需要断开链接
      else {
        _result.push(root.val)
        predecessor.right = null
        root = root.right
      }
    }
    // 如果没有左孩子,则直接访问右孩子
    else {
      _result.push(root.val)
      root = root.right
    }
  }

  return _result
}

本文分享自微信公众号 - 前端小书童(gaowenju_web),作者:前端小书童

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-09-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【一天一大 lee】求根到叶子节点数字之和 (难度:中等) - Day20201029

    给定一个二叉树,它的每个结点都存放一个 0-9 的数字,每条从根到叶子节点的路径都代表一个数字。

    前端小书童
  • 【一天一大 lee】 把二叉搜索树转换为累加树 (难度:简单)-Day20200921

    给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值...

    前端小书童
  • 【一天一大 lee】从中序与后序遍历序列构造二叉树 (难度:中等)-Day20200925

    因为后续遍历是先遍历左子树再遍历右子树最后遍历根节点, 那么右子树的索引一定大于左子树的索引,当不满足是说明节点遍历完成,终止递归

    前端小书童
  • 二叉树的遍历回顾

    本文重点在于复习并总结 二叉树每种遍历方式的递归与迭代实现,图片和示例代码均来自《邓俊辉-数据结构》。

    李拜六不开鑫
  • 二叉树的前中后序遍历

    前序遍历主要思想是什么呢?从根节点开始,前序遍历访问左子树,遇到空节点则返回,然后再前序遍历访问右子树,遇到空节点则返回。

    看、未来
  • 【戴嘉乐 IPFS】(入门)基于IPFS和Ngrok构建自维护资源网关

    由于一些特殊原因,ipfs.io网关在天朝无法访问,之前在外做宣讲的时候,也被很多朋友问到ipfs.io是否一直会被禁的问题,纷纷表示担忧,这边通过一个简单的D...

    圆方圆学院
  • 删除排序数组中的重复项

    给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

    _kyle
  • 如何根据二叉树的两种遍历方式重建二叉树(理论篇)

    我们知道,二叉树有三种不同的遍历方式:先序遍历,中序遍历和后序遍历。这三种遍历方式本质上是根据根节点的位置来命名的。根节点在前面,就是先序遍历;根节点在中间,就...

    青南
  • 数组:就移除个元素很难么?

    给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

    代码随想录
  • 什么时候可以用双指针,该咋用?

    双指针是我们做题中经常用到的思想,所以这个思想在刷题初期是一定要会的。其实我们早就学习过这个方法,那就是我们在学习数据结构的二分查找,下面我们通过二分查找来描述...

    灵魂画师牧码

扫码关注云+社区

领取腾讯云代金券