二叉树的下一个节点

题目描述

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

解法一：

最直接的想法是直接构造出二叉树的中序遍历，然后查看当前节点的下一个节点是什么。

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        ArrayList<TreeLinkNode> list = new ArrayList<TreeLinkNode>();
        TreeLinkNode root = pNode;
        //找到根节点，便于求中序遍历
        while(root.next != null) {
            root = root.next;
        }
        getInfix(root, list);
        int i = 0;
        //查找pNode在中序遍历中的位置
        for(; i < list.size(); i++) {
            if(list.get(i) == pNode) {
                break;
            }
        }
        //输出pNode的下一个节点
        if(i + 1 < list.size()) {
            return list.get(i + 1);
        }
        else {
            return null;
        }
    }
    //求中序遍历
    public void getInfix(TreeLinkNode pNode, ArrayList<TreeLinkNode> list) {
        if(pNode != null) {
        getInfix(pNode.left, list);
        list.add(pNode);
        getInfix(pNode.right, list);
        }
    }
}

解法二：

但是很明显解法一要占用额外的空间，且当树很大的时候效率很低。

其实求下一个节点时，例如2的下一个节点，我们很容易便可以看出是3，而无需考虑整体的排序结果，那么有没有办法直接得到每个点的下一个节点呢？

我们可以将二叉树中的点进行分类，由于是中序遍历，一个点的下一个节点只可能出现在自己的上方或者右子树中，不可能出现在左子树中，我们可以将节点分为

1、含有右子树的节点

例如节点3。这种节点的下一个节点必定为右子树的最左边的节点。

2、不含有右子树的节点

（1）为父节点的左子节点。

例如节点2。这种节点的下一个节点必定为自己的父节点。

（2）为父节点的右子节点。

例如节点9。求这种节点的下一个节点，应一直往上找，直到找到一个点A，A是A.parent的左子节点，则所求的下一节点则为A.parent

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode == null) {
            return pNode;
        }
        TreeLinkNode res = null;
        //含有右子树的节点
        if(pNode.right != null) {
            pNode = pNode.right;
            while(pNode.left != null) {
                pNode = pNode.left;
            }
            res = pNode;
        }
        else {   
                //不含右子树且为父节点的左子节点
            if(pNode.next != null && pNode.next.left == pNode) {
                res = pNode.next;
            }
            else {
                //不含右子树且为父节点的右子节点
                while(pNode.next != null && pNode == pNode.next.right) {
                    pNode = pNode.next;
                }
                res = pNode.next;
            }
        }
        return res;
    }

}