二叉树的下一个结点

题目描述

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

解题思路

中序遍历规则--》左根右。

所以存在两大类情况：

• 右子树存在，下一结点就是右子树最左下结点；

• 右子树不存在，也有两类：

  • 是父结点的左孩子，下一结点就是父结点；

  • 是父节点的右孩子，递归找父节点，直到所在树是其父结点的左子树，下一结点就是此结点。

代码

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;
        } else {
            while (pNode.next != null && pNode.next.left != pNode)
                pNode = pNode.next;
            return pNode.next;
        }
    }
}
​