前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >在二叉树中找到一个节点的后继节点

在二叉树中找到一个节点的后继节点

原创
作者头像
大学里的混子
修改2019-02-19 16:35:36
1.2K0
修改2019-02-19 16:35:36
举报
文章被收录于专栏:LeetCodeLeetCode

在二叉树中找到一个节点的后继节点

现在有一种新的二叉树节点类型如下:

代码语言:javascript
复制
public class Node {
public int value;
public Node left;
public Node right; 
public Node parent;
public Node(int data) { 
    this.value = data; 
    }
} 

该结构比普通二叉树节点结构多了一个指向父节点的parent指针。 假设有一 棵Node类型的节点组成的二叉树, 树中每个节点的parent指针都正确地指向自己的父节点, 头节点的parent指向null。 只给一个在二叉树中的某个节点 node, 请实现返回node的后继节点的函数。 在二叉树的中序遍历的序列中, node的下一个节点叫作node的后继节点。

代码语言:javascript
复制
class PNode {
     public int value;
     public PNode left;
     public PNode right;
     public PNode parent;
     public PNode(int data) {
         this.value = data;
     }
 }

 public static PNode getSuccessorNode(PNode node){
     if (node == null) return node;
     if (node.right != null) return mostLeftNode(node.right);
     else {
         PNode parent = node.parent;
         while (parent != null && parent.left != node){
             node = parent;
             parent = node.parent;
         }
         return parent;
     } 
 }

 public static PNode mostLeftNode(PNode node){
     if (node == null) return node;
     while (node.left != null){
         node = node.left;
     }
     return node;
 }

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档