题解 | #二叉树的下一个结点#

这题真的感觉有些吃力，看了各方的题解才勉强能够做，说实话，二叉树的题还是有些晕的， 重回本题，二叉树的中序遍历就是左子树，根节点，右子树。 如图二叉树，5的下一个节点是6，7的下一个节点是5。 所以分为两种情况： 第一种：节点有右子树，那么该节点的下一个节点就是右子树的最左节点 第二种：节点没有右子树，像节点4，节点6，节点7都没有右子树，4和6为父节点的左节点，那么他们的下一节点就是父节点，而7是父节点的右节点，那么就向上找父节点，当为父节点的父节点的左子树时，它的下一个节点就是父节点。

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