剑指offer—二叉树中序遍历的下一个节点 解答

剑指offer—二叉树中序遍历的下一个节点

题目描述

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

思路

你一开始可能会想到使中序遍历去做,但是仔细思考一下,那样还要从头开始遍历一遍,我们不妨自己从当前需要判断的节点开始找一找思路。

我们可以发现当前节点一个有两种可能:

  1. 它的右边节点不为空

    这个时候我们需要对它右边的节点进行“半次中序遍历”

对当前节点右节点进行中序遍历时,完全不用管右节点的右子树,因为找中序遍历的下一个节点,如果右节点的左子树都为空的话就返回右节点这个节点,不会走到右子树,所以称为“半中序遍历”

  1. 它的右边节点为空

    这时我们根据中序遍历的规则,知道该节点的左子树都被遍历了,右子树为空,所以只能从父亲节点开始判断

    1. 如果当前节点为父亲节点的左节点,那么中序遍历的下一个节点就是该父亲节点(左根右)
    1. 如果当前节点为父节点的右节点,那么此时父亲节点已经被遍历过,当前节点的左子树也被遍历过,右边节点为空,根据中序遍历规则需要去对父节点的父节点执行类似操作,判断父节点是否为父父节点的左孩子,如果是返回父父节点,如果是右孩子,还需要往上继续执行这样的操作判断,如果判断到根节点还是不满足条件,就返回null

代码

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;//不知道为什么next代表父节点,吐槽牛客一波

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode){
        TreeLinkNode p,r;
        if((r=pNode.right)!=null){
            while(r.left!=null) r = r.left;
            return r;
        }else{
            while(pNode!=null){
                p = pNode.next;
                if(p!=null&&p.left==pNode) return p;
                else pNode = p;
            }
            return null;
        }
    }
}