Java iterative and recursive solutions.


  • 0
    C
    // iteratively 
    public TreeNode inorderSuccessor1(TreeNode root, TreeNode p) {
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode ret = null;
        TreeNode pre = null;
        while (true) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (stack.isEmpty()) {
                break;
            }
            TreeNode node = stack.pop();
            if (pre == p) {
                ret = node;
                break;
            }
            pre = node;
            root = node.right;
        }
        return ret;
    }
    
    // recursively
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        List<TreeNode> ret = new ArrayList<>();
        ret.add(null);
        List<TreeNode> pre = new ArrayList<>();
        pre.add(null);
        dfs(root, p, pre, ret);
        return ret.get(0);
    }
    
    private void dfs(TreeNode root, TreeNode p, List<TreeNode> pre, List<TreeNode> ret) {
        if (root != null) {
            dfs(root.left, p, pre, ret);
            if (pre.get(0) == p) {
                ret.set(0, root);
            }
            pre.set(0, root);
            dfs(root.right, p, pre, ret);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.