[剑指Offer]8-二叉树的下一个节点

链接

https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&tPage=3&rp=3&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

题意

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

解题思路

递归。

根据“左根右”，分：

1.根->右

2.左->根

3.“左”->根

三种情况讨论。

代码（C++）

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
        if(!pNode){
            return nullptr;
        }        if(pNode->right){
            pNode=pNode->right;
            while(pNode->left){//
                pNode=pNode->left;
            }
            return pNode;
        }        if(pNode->next&&pNode->next->left==pNode){//
            return pNode->next;
        }        while(pNode->next&&pNode->next->left!=pNode){
            pNode=pNode->next;
        }
        if(pNode->next){
            return pNode->next;
        }
        else{
            return nullptr;
        }
    }
};

代码(Java)

public class Main {
public static void main(String args[]) {
Node n1=new Node(1);
Node n2=new Node(2);
Node n3=new Node(3);
Node n4=new Node(4);
n1.left=n2;n2.next=n1;
n1.right=n3;n3.next=n1;
n3.left=n4;n4.next=n3;
Node nextNode=getNextNode(n2);
if(nextNode!=null) {
System.out.print(nextNode.val);
}
}public static Node getNextNode(Node curNode) {
if(curNode==null) {
return null;
}
if(curNode.right!=null) {
Node node=curNode.right;
while(node.left!=null) {
node=node.left;
}
return node;
}if(curNode.next!=null&&curNode.next.left==curNode) {
return curNode.next;
}while(curNode.next!=null) {
if(curNode.next.left==curNode) {
return curNode.next;
}
}return null;
}
}