剑指Offer系列（java版，详细解析）08.二叉树的下一个节点

蔚落 2022-10-23 07:00 107阅读 0赞

# 题目描述 #

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

节点代码如下：

/** * 二叉树节点 * @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;
        }
    }