剑指offer---二叉树的下一个结点 

题目描述

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

解题思路

解题思路(分三种情况):

中序遍历{d,b,h,e,i,a,f,c,g}

1. 如果当前结点有右子树
下一个节点就是它的右子树的最左子节点(从右子节点出发一致沿着指向左子节点的指针,即可找到)
如:b ——》h, a——》f

2. 如果当前节点没有右子树
(1) 如果当前节点是它父节点的左子节点
下一个节点就是它的父节点
如:d——》b, f——》c, h——》e

(2)如果当前节点是它父节点的右子节点
沿着指向父节点的指针一直向上遍历,直到找到一个是它父节点的左子节点的节点,如果这样的节点存在,那么这个节点的父节点就是我们要找到的下一个节点
如:i节点的下一个节点:沿着指向父节点的指针向上遍历,先到e,e是b的右子节点,不是,继续向上遍历,到b, b是a的左子节点,因此节点b的父节点a就是i的下一个节点

如:g节点的下一个节点:沿着指向父节点的指针向上遍历,先到c, c是a的右子节点,不是,继续向上遍历到a, a是根节点,无父节点,因此g没有下一个节点。

代码

// 题目:给定一棵二叉树和其中的一个结点,如何找出中序遍历顺序的下一个结点?
// 树中的结点除了有两个分别指向左右子结点的指针以外,还有一个指向父结点的指针。
 
public class NextNodeInBinaryTrees {
    private class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode parent = null;
 
        TreeLinkNode(int val) {
            this.val = val;
        }
    }
 
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null) {
            System.out.print("结点为null ");
            return null;
        }
        if (pNode.right != null) {
            pNode = pNode.right;
            while(pNode.left!=null)
                pNode=pNode.left;
            return pNode;
        }
        while(pNode.parent !=null){
            if(pNode==pNode.parent .left)
                return pNode.parent;
            pNode=pNode.parent;
        }
        return null;
    }