56 二叉树的下一个结点

题目描述

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

代码一

思想
非常好理解,找到根节点,然后对二叉树中序遍历,添加到arrlist里面去.

public class Solution {
    ArrayList<TreeLinkNode> list = new ArrayList<TreeLinkNode>();
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        TreeLinkNode root = pNode;
        //找根节点
        while(root.next!=null) {
            root = root.next;
        }
        //然后对该二叉树中序遍历
        MidedleOrder(root);
        for(int i=0;i<list.size();i++) {
            if(pNode==list.get(i)) {
                return i==list.size()-1?null:list.get(i+1);
            }
        }
        return null;
    }
    public void MidedleOrder(TreeLinkNode root) {
        if(root!=null) {
            MidedleOrder(root.left);
            list.add(root);
            MidedleOrder(root.right);
        }
    }
}

代码二

思想

仔细观察，可以把中序下一结点归为几种类型：

1. 有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H
   
2. 无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E
   

3. 无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A；例如 G，并没有符合情况的结点，所以 G 没有下一结点
   

   public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode==null)return null;
        TreeLinkNode pNext = null;
        //如果一个节点有右子树的时候，那么它的下一个节点就是它的右子树中的最左子节点。
        if(pNode.right!=null) {
            TreeLinkNode pRight = pNode.right;
            while(pRight.left!=null) {
                pRight = pRight.left;
            }
            pNext = pRight;
        }
        //如果一个节点没有右子树的时候
        else if(pNode.next!=null) {
            TreeLinkNode pCurrent = pNode;
            TreeLinkNode pParent = pNode.next;
            //如果它是父节点的右节点的话,那么我们就一只向上找父节点,直到找到的父节点不是它父节点的右节点
            //如果它不是父节点的右节点的话,那么直接返回父节点
            while(pParent!=null&&pCurrent==pParent.right) {
                pCurrent = pParent;
                pParent = pParent.next;
            }
            pNext = pParent;
        }        
        return pNext;
    }