推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

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

/* 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)
    {
   
        
    }
}

参考思路:

首先要知道中序遍历:左右根。

然后再考虑几种情况:

  1. 二叉树为空,直接返回 null 即可。
  2. 如果该结点有右子树,则找该右子树的最左节点。
  3. 如果该结点没有右子树,则向上找,一直找到第一个是其父结点的左孩子的结点;
    如果一直到根结点都没找到,说明该结点是中序遍历的最后一个结点,返回 nulll 即可。

参考实现:

/* 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)
    {
   
        if (pNode == null){
   
            return null;
        }
        if (pNode.right != null) {
   
            pNode = pNode.right;
            while (pNode.left != null) {
   
                pNode = pNode.left;
            }
            return pNode;
        }
        while(pNode.next != null) {
   
            if (pNode.next.left == pNode) {
   
                return pNode.next;
            }
            pNode = pNode.next;
        }
        return null;
    }
}

看完之后,如果还有什么不懂的,可以在评论区留言,会及时回答更新。

这里是猿兄,为你分享程序员的世界。

非常感谢各位大佬们能看到这里,如果觉得文章还不错的话, 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用!!!

注: 如果猿兄这篇博客有任何错误和建议,欢迎大家留言,不胜感激!