jd0406.后继者

题目描述

设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回null。

示例1:

输入: root = [2,1,3], p = 1

  2
 / \
1   3

输出: 2

示例2:

输入: root = [5,3,6,2,4,null,null,1], p = 6

      5
     / \
    3   6
   / \
  2   4
 /   
1

输出: null

题解

DFS + 迭代

题目中已经说明了是中序遍历的后继者, 所以在中序遍历的基础上进行操作

这里用迭代的方法完成.

根据二叉树的中序遍历的迭代过程可知, 每遍历完一个节点, 下面遍历到的元素一定是栈中下一个将要弹出的节点. 所以思路就是遍历的过程中如果遇到了目标节点, 就把下一个将要出栈的节点弹出即可.

具体的做法就是在中序遍历过程的基础上添加一个布尔变量, 初始值为false, 每次出栈时都检查一下是否是true, 若为true就把弹出的节点返回. 如果在遍历过程中遇到了目标节点, 就把该布尔变量变为true, 那么下一个节点就会返回.

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    if (root == null) {
        return null;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    boolean flag = false;

    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }

        cur = stack.pop();
        if (flag)
            return cur;
        if (cur.val == p.val) {
            flag = true;
        }
        cur = cur.right;

    }

    return null;
}