二叉树的下一个节点

题目描述

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

分析

  1. 如果右子树不为空,则下一节点为右子树最左边的节点。
  2. 如果右子树为空,如果父节点为空,则返回空。
  3. 如果该节点是其父节点的左孩子,则返回其父节点。
  4. 否则依次往上找父节点,知道某个节点是其父节点的左孩子,返回该节点的父节点

代码:

public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode){
if (pNode == null) return null;
if (pNode.right != null) {
TreeLinkNode node = pNode.right;
while (node.left != null) node = node.left;
return node;
}
if (pNode.next == null) return null;
if (pNode == pNode.next.left) return pNode.next;
TreeLinkNode node = pNode.next;
while (node.next != null && node != node.next.left) node = node.next;
if (node.next != null) return node.next;
return null;
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD's Blog All Rights Reserved.

访客数 : | 访问量 :