二叉树的下一个结点
题目描述
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 ***
思路
一道概念题吧，就是考考中序遍历。本题一共就两种情况
- 一种是有右儿子，然后找右子树中最左的结点
- 另一种是它所在的子树是某个结点的左子数，就是一路向上找，先判断自己是不是父亲结点的左儿子，不是，移动父亲结点，再判断自己是不是父亲结点的左儿子。如果找不到就返回null。找到了就返回那个父亲结点。 要记住先判断读入结点是否为null。不能被坑了。
Java实现
/*
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 null;
}
if(pNode.right!=null){
pNode=pNode.right;
while(pNode.left!=null){
pNode=pNode.left;
}
return pNode;
}
while(pNode.next!=null){
if(pNode.next.left==pNode){
return pNode.next;
}
pNode=pNode.next;
}
return null;
}
}
