[数据结构与算法]【二叉树】【打卡54天】《剑指Offer》2刷:JZ8 二叉树的下一个结点

1、题目描述

给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。下图为一棵有9个节点的二叉树。树中从父节点指向子节点的指针用实线表示，从子节点指向父节点的用虚线表示

?

?

2、算法分析

题目求得是二叉树中中序遍历当前结点的下一个结点。

①当前结点存在右孩子结点，那就看一下右孩子结点是否有左孩子结点，有的话就继续遍历它的左孩子结点。

②当前结点不存在右孩子，那么它存在左孩子对它来说并没什么卵用，那就往父节点上找。也分一下。

? ? <1>当前结点是当前结点父节点的左孩子结点，那么当前结点的下一个结点就是其父节点。

? ? <2>当前结点是当前结点父节点的右孩子结点，且当前结点没有右孩子。那么当前结点的下一个结点就是其父父节点的父节点。

注意：pNode.next结点是指向当前结点的父节点

具体看下代码实现：

3、代码实现

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
//pNode是当前结点
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        // 1.判断当前结点是否为空
        if(pNode == null){
            return null;
        }
        // 当前结点有右孩子结点
        if(pNode.right != null){
               pNode = pNode.right;
               while(pNode.left != null){
                    pNode = pNode.left;
               }
            return  pNode;
        }
        // 当前结点没有右孩子节点,pNode.next是当前结点的父节点
        while(pNode.next != null){
            if(pNode == pNode.next.left){
                return pNode.next;
            }
            pNode = pNode.next;
        }
       return null;
    }
}