【530. 二叉搜索树中的最小绝对差】

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:

Input: root = [4,2,6,1,3]
Output: 1

Example 2:

Input: root = [1,0,48,null,null,12,49]
Output: 1

Constraints:

  • The number of nodes in the tree is in the range [2, 104].
  • 0 <= Node.val <= 105
  • Note: This question is the same as 783: Minimum Distance Between BST Nodes – LeetCode


    这题求BST中任意两个子节点的最小差。其实跟上一题挺像的,也是需要记录全局的最小和上一次遍历的节点,利用BST的性质(inorder)进行递归。然而自己写的时候出现了以下几个问题:

    1. if (root == null)时,需要return min,刚开始直接return 0了……

    2. 刚开始写成了直接return Math.min(f(left), f(right)),submit完发现WA了,看了答案才发现需要严格进行inorder traversal,我这直接写成preorder了无法preserve order。

    3. 另外也看到有人指出用全局变量其实不太好,如果要改成传函数参数的话,需要参数是mutable的,方便一边遍历一边更新。可以参考这个,用长度为1的array来保存:Java O(n) Time Inorder Traversal Solution – Minimum Absolute Difference in BST – LeetCode

    2023.2.4

    做783的时候再次遇到这个题,瞎写一通上来就WA,然后毫无思路,真不知道上次咋写的……

    从头开始想一遍思路,大概就是既然我们要找最小差的两个数之差,那么由于它是BST,最小差肯定是在两个inorder traversal的相邻节点之间,于是相当于就只需要找相邻的两个节点之间的差值,于是需要一个prev来记录上次的节点。 

    感觉就是,不需要想的太复杂,以跟prev比较为核心,所以在prev那段需要min = Math.min,而递归左右两边的时候都不需要。

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        TreeNode prev = null;
        int min = Integer.MAX_VALUE;
        public int getMinimumDifference(TreeNode root) {
            if (root == null) {
                return min;
            }
            min = getMinimumDifference(root.left);
            if (prev != null) {
                min = Math.min(min, Math.abs(root.val - prev.val));
            }
            prev = root;
            min = getMinimumDifference(root.right);
            return min;
        }
    }

    迭代:

    其实就是inorder的迭代方法,which早就忘了,这次就复习了一下。刚开始写成preorder了看了半天都不对……以及还是得用到prev啊。

    2023.2.4

    半抄答案地写出来了……嗯……就是记了个大概,但是没理解透吧。刚开始想了半天从stack里可以直接pop还是得先peek……果然还是脑子不清醒,对这个问题没有理解透彻。以及本来好好一个inorder一加上要判断min就又不会了……太蠢了……

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        TreeNode prev = null;
        int min = Integer.MAX_VALUE;
        public int getMinimumDifference(TreeNode root) {
            if (root == null) {
                return min;
            }
            Deque<TreeNode> stack = new ArrayDeque<>();
            pushAllLeftNodes(root, stack);
            while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                if (prev != null) {
                    min = Math.min(min, Math.abs(node.val - prev.val));
                }
                pushAllLeftNodes(node.right, stack);
                prev = node;
            }
            return min;
        }
    
        private void pushAllLeftNodes(TreeNode node, Deque<TreeNode> stack) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
        }
    }

    物联沃分享整理
    物联沃-IOTWORD物联网 » 【530. 二叉搜索树中的最小绝对差】

    发表评论