剑指offer4J【C2 P8】二叉树的下一个节点

题目

给定一个二叉树与其中一个节点（目标节点），找到中序遍历中的下一个节点(子节点中包含父节点的引用)

题解

解法1：从根节点中序遍历，遍历至目标节点，继续向下遍历一次，取得结果。
此解法缺点就是没有很好的利用子节点中的父节点属性，时间复杂度相对较高

解法2：

• 中序遍历 秉承着左根右的规律，即存在两种情况
  • 存在右节点
  • 不存在右节点
• case1：存在右节点
  存在右节点，我们只要找右节点的最左孩子即可（包括它自己）
• case2：不能存在右节点
  即我们遍历的节点已经达到该分支的右边界，那么我们只要反向找到该节点的父节点。
  • 如果父节点 是爷爷节点（父节点的父节点）左孩子，即代表当前左已经全部遍历完成，该遍历根了，爷爷节点即是下一个结果。
  • 如果父节点 是爷爷节点的右孩子，那么继续向上找，即父亲节点作为当前节点重复case2逻辑。

    public DetailTreeNode findNextInOrder(DetailTreeNode root, DetailTreeNode node) {
        if (node == null || root == null) return null;
        DetailTreeNode data;
        if (node.getRight() != null) {
            data = node.getRight();
            while (data.getLeft() != null) {
                data = data.getLeft();
            }
            return data;
        }
        data = node.getParent();
        while (data != null && node != data.getLeft()) {
            node = data;
            data = data.getParent();
        }
        return data;
    }

源码: 剑指offer4J