【JZOF】08 二叉树的下一个结点

描述:

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示.

题解：
https://blog.nowcoder.net/n/737a842c39d6473db2a10d4f1de7610c?f=comment

方法一：

现根据给定节点找到root，然后从root开始中序遍历，保存中序的结果，然后再遍历一遍中序的结果，比较并输出当前节点的下一个节点。

方法二：分类直接寻找

思路：

直接寻找分为三种情况

1.如果给出的结点有右子节点，则最终要返回的下一个结点即右子树的最左下的结点。
2.如果给出的结点无右子节点，且当前结点是其父节点的左子节点，则返回其父节点。
3.如果给出的结点无右子节点，且当前结点是其父节点的右子节点，则先要沿着左上方父节点爬树，一直爬到当前结点是其父节点的左子节点为止，返回的就是这个父节点；或者没有满足上述情况的则返回为NULL。

具体做法：

step 1：判断该节点是否符合思路中第一点，则一直找到右子树的左下节点为返回值
step 2：判断该节点是否符合思路中第二点，则返回当前节点的父亲节点
step 3：判断该节点是否符合思路中第三点，则迭代向上找父节点，直到迭代的当前节点是父节点的左孩子节点为止，返回该父节点；如果不满足上述情况返回NULL

import java.util.*;
public class Solution {
    
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
    
        // 情况一
        if(pNode.right != null) {
    
            TreeLinkNode rchild = pNode.right;
            // 一直找到右子树的最左下的结点为返回值
            while(rchild.left != null) rchild = rchild.left; 
            return rchild;
        }
        
        // 情况二
        if(pNode.next != null && pNode.next.left == pNode) {
    
            return pNode.next;
        }
        
        // 情况三
        if(pNode.next != null) {
    
            TreeLinkNode ppar = pNode.next;
            // 沿着左上一直爬树，爬到当前结点是其父节点的左结点为止
            while(ppar.next != null && ppar.next.right == ppar) ppar = ppar.next; 
            return ppar.next;
        }
        return null;
    }
}