剑指offer_二叉树---二叉树的下一节点

简介: 剑指offer_二叉树---二叉树的下一节点

##题目描述

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

##解题思路

1,因为是中序遍历,顺序为左—中----右

2,因为考虑下一个节点,所以考察范围可以缩小到中和右

3,如果当前节点有右子树,那么下一个节点就是右子树的最左节点

4,如果当前节点没有右子树,且是父节点的左子节点,则下一个节点就是自己的父节点

5,如果当前节点没有右子树,且是父节点的右子节点,则向上找到第一个是其父节点左子节点的节点,下一个节点就是该父节点

##代码

/**
 * 
 */
package offerTest;
/**
 * <p>
 * Title:Next
 * </p>
 * <p>
 * Description:
 * </p>
 * 
 * @author 田茂林
 * @data 2017年8月21日 上午10:34:53
 */
class TreeLinkNode {
  int val;
  TreeLinkNode left = null;
  TreeLinkNode right = null;
  TreeLinkNode next = null;
  TreeLinkNode(int val) {
    this.val = val;
  }
}
public class Next {
  public TreeLinkNode GetNext(TreeLinkNode pNode) {
    if (pNode == null) {
      return null;
    }
    // 如果当前节点有右子树
    if (pNode.right != null) {
      TreeLinkNode p = pNode.right;
      while (p.left != null) {
        p = p.left;
      }
      return p;
    } else { // 如果当前节点没有右子树,且是父节点的左子节点
      if (pNode.next != null) {
        TreeLinkNode pcur = pNode;
        TreeLinkNode parent = pcur.next;
        if (parent != null && pcur == parent.left) { 如果当前节点没有右子树,且是父节点的左子节点,则下一个节点就是自己的父节点
          return parent;
        }
        while (parent != null && pcur == parent.right) {如果当前节点没有右子树,且是父节点的右子节点,则向上找到第一个是其父节点左子节点的节点,下一个节点就是该父节点
          pcur = parent;
          parent = pcur.next;
        }
        return parent;
      }
    }
    return null;
  }
}


相关文章
剑指offer_二叉树---二叉搜索树的第k个结点
剑指offer_二叉树---二叉搜索树的第k个结点
73 0
剑指offer 07. 二叉树的下一个节点
剑指offer 07. 二叉树的下一个节点
70 0
剑指offer-7.二叉树的下一个节点
剑指offer-7.二叉树的下一个节点
47 1
|
算法
剑指offer_二叉树---平衡二叉树
剑指offer_二叉树---平衡二叉树
90 0
剑指offer之二叉搜索树的第K个节点
剑指offer之二叉搜索树的第K个节点
108 0
剑指offer_二叉树---重建二叉树
剑指offer_二叉树---重建二叉树
72 0
剑指offer_二叉树---二叉搜索树的后序遍历
剑指offer_二叉树---二叉搜索树的后序遍历
76 0
剑指offer_二叉树---二叉搜索树与双向链表
剑指offer_二叉树---二叉搜索树与双向链表
71 0
剑指offer_二叉树---二叉树的镜像
剑指offer_二叉树---二叉树的镜像
54 0
剑指offer_二叉树---二叉树的深度
剑指offer_二叉树---二叉树的深度
90 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等