[剑指Offer]8-二叉树的下一个节点
链接
题意
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
解题思路
递归。
根据“左根右”，分：
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;
}
}