专栏首页code秘密花园【算法专栏】二叉树的下一个节点

【算法专栏】二叉树的下一个节点

本系列是《剑指offer》或leetcode的JavaScript版本。 每期1-2个算法,也有可能是一个类别。 文章包括题目、思路以及代码。 如果您对本期有不同或者更好的见解,请后台留言,喜欢请点个好看,谢谢阅读。

题目

给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

思路

中序遍历的顺序 左 - 根 - 右

所以寻找下一个节点的优先级应该反过来 优先级 右 - 根 - 左

  • 右节点不为空 - 取右节点的最左侧节点
  • 右节点为空 - 如果节点是父亲节的左节点 取父节点
  • 右节点为空 - 如果节点是父亲节的右节点 父节点已经被遍历过,再往上层寻找...
  • 左节点一定在当前节点之前被遍历过

以下图的二叉树来分析:

中序遍历:CBDAEF

  • B - 右节点不为空,下一个节点为右节点D
  • C - 右节点为空,C是父节点的左节点,取父节点B
  • D - 右节点为空,D是父节点的右节点,再往上蹭分析,B是其父节点的左节点,取B的父节点A
  • F - 右节点为空,F是父节点的右节点,没有符合条件的节点,F为遍历的最后一个节点,返回null

代码

/*function TreeLinkNode(x){
        this.val = x;
        this.left = null;
        this.right = null;
        this.next = null;
    }*/
    function GetNext(pNode) {
      if (!pNode) {
        return null;
      }
      if (pNode.right) {
        pNode = pNode.right;
        while (pNode.left) {
          pNode = pNode.left;
        }
        return pNode;
      } else {
        while (pNode) {
          if (!pNode.next) {
            return null;
          } else if (pNode == pNode.next.left) {
            return pNode.next;
          }
          pNode = pNode.next;
        }
        return pNode;
      }
    }

考察点

  • 二叉树
  • 复杂问题拆解

本文分享自微信公众号 - code秘密花园(code_mmhy),作者:ConardLi

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

原始发表时间:2019-07-31

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 前端应该如何准备数据结构和算法?

    据我了解,前端程序员有相当一部分不是科班出身,以至于对“数据结构”和“算法”的基础概念都不是很清晰,这直接导致很多人在看到有关这部分的内容就会望而却步。

    ConardLi
  • 《剑指offer》第11期:两个链表题目

    简单思路: 循环到链表末尾找到 length 在找到length-k节点 需要循环两次。

    ConardLi
  • 《剑指offer》11.链表中倒数第k个节点

    简单思路: 循环到链表末尾找到 length 在找到length-k节点 需要循环两次。

    ConardLi
  • JavaScript 技术篇-js只获取本节点text文本,不包含子节点

    innerText 和 textContent 都是获取所有节点的 firstChild.nodeValue 是获取本节点的text文本,不包含子节点的。

    小蓝枣
  • 什么是一致性Hash算法?

    可以将传入的 Key 按照 index=hash(key)%N 这样来计算出需要存放的节点。其中 hash 函数是一个将字符串转换为正整数的哈希映射方法,N 就...

    Java3y
  • Zookeeper系列(5) —— Zookeeper 常用的客户端操作命令

    创建节点的命令格式 create [-s] [-e] /path data acl

    求和小熊猫
  • 网页结构的简介和Xpath语法的入门教程

    相信很多小伙伴已经听说过Xpath,之前小编也写过一篇关于Xpath的文章,感兴趣的小伙伴可以戳这篇文章如何利用Xpath抓取京东网商品信息以及Python网络...

    Python进阶者
  • 第15期:索引设计(索引组织方式 B+ 树)

    谈到索引,大家并不陌生。索引本身是一种数据结构,存在的目的主要是为了缩短数据检索的时间,最大程度减少磁盘 IO。

    爱可生开源社区
  • 用Golang写一个搜索引擎

    本篇较长较枯燥,请保持耐心看完。 前面两章介绍了一下倒排索引以及倒排索引字典的两种存储结构,分别是 跳跃表 和 哈希表 ,本篇我们介绍另一种数据结构,他也被大量...

    李海彬
  • MySQL级联复制中的数据同步(r11笔记第20天)

    最近开发的同事反馈了一个问题,说有一台北京节点的MySQL数据库数据延迟太大,想让我们帮忙看看怎么解决。 这个问题一下子让我想起了之前“水深火热...

    jeanron100

扫码关注云+社区

领取腾讯云代金券