程序员社区

剑指Offer系列(java版,详细解析)08.二叉树的下一个节点

题目描述

给定一个二叉树和其中的一个节点,如何找出中序遍历序列的下一个节点?。注意,树中的节点不仅包含左右子节点,同时包含指向父节点的指针。

节点代码如下:

/** * 二叉树节点 * @Author rex * 2018/6/13 */
public class TreeLinkNode {
   
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    // 父节点
    TreeLinkNode parent = null;

    TreeLinkNode(int val) {
   
        this.val = val;
    }
}

测试用例

  • 普通二叉树(完全二叉树;不完全二叉树)。
  • 特殊二叉树(所有的节点都没有右子节点的二叉树;所有节点都没有左子节点的二叉树;只有一个节点的二叉树;二叉树的根节点指针为null)。
  • 不同位置的节点的下一个节点(下一个节点为当前节点的右子节点、右字数的最左子节点、父节点、跨层的父节点等;当前节点没有下一个节点)

题目考点

  • 考察应聘者对二叉树中序遍历的理解程度。
  • 考察应聘者分析复杂问题的能力。应聘者只有画出二叉树的结构图、通过具体的例子找出中序遍历下一个节点的规律,才有可能设计出可行的算法。(感觉上找规律很重要)

解题思路

通过对下一个节点的情况分析,主要有以下两种情况:

  • 如果一个节点的右子树不为空,那么该节点的下一个节点是右子树的最左节点。如下图:
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JarriXLu-1615390886622)(https://raw.githubusercontent.com/todorex/Coding-Interviews/master/images/offer8-1.png)]

  • 如果一个节点的右子树为空,那么需要沿着父节点的指针一直向上遍历,知道找到一个是它父节点的左子节点的节点。如果这样的节点存在,那么这个节点的父节点就是我们要找的下一个节点。如下图:
    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UOQIrT64-1615390886623)(https://raw.githubusercontent.com/todorex/Coding-Interviews/master/images/offer8-2.png)]

自己解题

没有进行详细的分析,没有找规律,没有做出来!!!!

参考解题

/** * 二叉树的下一个节点 * * @Author rex * 2018/6/13 */
public class Solution {
   

    /** * 寻找二叉树的下一个节点 * * @param pNode * @return */
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
   
        if (pNode == null) {
   
            return null;
        }
        // 第一种情况
        if (pNode.right != null) {
   
            TreeLinkNode rNode = pNode.right;
            while (rNode.left != null) {
   
                rNode = rNode.left;
            }
            return rNode;
        } else {
   
            // 第二种情况
            while (pNode.parent != null) {
   
                TreeLinkNode parentNode = pNode.parent;
                if (parentNode.left == pNode) {
   
                    return parentNode;
                }
                pNode = pNode.parent;

            }

        }
        return null;
    }
}
赞(0) 打赏
未经允许不得转载:IDEA激活码 » 剑指Offer系列(java版,详细解析)08.二叉树的下一个节点

一个分享Java & Python知识的社区