中序遍历

1、中序遍历根节点的左子树；

2、访问根节点；

3、中序遍历根节点的右子树；

中序遍历结果：dbheiafcg

问题描述

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

思路及代码

三种情况：

1、该结点有右子树，则下一结点为右子树中序遍历的最左节点；

2、该结点无左子树&&父节点不为空{

caseA:该节点为父节点的左节点，则下一节点为父节点；

caseB:该结点为父节点的右节点，则向上遍历至当前结点为父节点的左节点（非右节点），则当前结点的父节点为下一节点；

或一直向上遍历到当前结点无父节点，则当前结点无下一节点。

}

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode == null)
            return pNode;
        //case 1 该结点有右子树
        TreeLinkNode pNext = null;
         if(pNode.right != null){
             TreeLinkNode p1= pNode.right;
             while(p1.left!= null){
                 p1= p1.left;
             }
              pNext= p1;
         }else{
        //case 2 该结点无右子树
        //该结点为父节点的左结点，则该父节点就是下一个结点
        //该结点为父节点的右节点，则向上遍历至当前结点为父节点的左结点或无父节点
           if( pNode.next != null){
            TreeLinkNode current = pNode;
            TreeLinkNode parent = pNode.next;
            while(current.next!=null && parent.right == current){
                current = parent;
                parent = parent.next;
            }
            pNext= parent;
        }
         }
        return pNext;
    }
}