LeetCode 285 & 510. 二叉树中序后继 I & II

题目详见:LettCode 285. Inorder Successor in BST

解法一

思路

由于从根节点开始,我们可以利用中序遍历的迭代写法,并加入一个 prev 节点记录上一次访问的节点。当上一次访问的节点值和目标节点值相同时,当前遍历的节点就是我们要找的后继。

代码
class Soution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        if (root == null) return null;

        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        TreeNode prev = null;
        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if (prev != null && prev.val == p.val) {
                return curr;
            }
            prev = curr;
            curr = curr.right;
        }
        return null;
    }
}
复杂度分析
  • 时间复杂度
    • O(H) 遍历整个树
  • 空间复杂度
    • O(H) to keep the stack

题目详见:510. Inorder Successor in BST II

解法一

思路

这道题没有从根节点出发,而是需要直接找出一个节点的后继。此时要分两种情况讨论。

因为中序遍历的顺序是 左 - 根 - 右,所以如果目标节点有右孩子,我们先将指针移动到右孩子,随后一直寻找该节点的左孩子,直到没有左孩子为止。
如果目标节点没有右孩子,那么需要一直向上回溯,直到找到一个节点,是父节点的左孩子,那么这个父节点就是后继。

代码
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
};
*/
class Solution {
    public Node inorderSuccessor(Node node) {
        if (node.right != null) {
            node = node.right;

            while (node.left != null) {
                node = node.left;
            }

            return node;
        }

        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }

        return node.parent;
    }
}
复杂度分析
  • 时间复杂度 O(H)
  • 空间复杂度 O(1)

TakeAway

  • 第二题不知道这个节点在那个位置,所以需要针对 inorder traversal 的性质来解题。
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!