题目描述

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

节点代码如下：

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