CY-Left

LeetCode基本功底

[leetcode]Minimum Distance Between BST Nodes

原文&翻译

Given a Binary Search Tree (BST) with the root node root, return the minimum difference between the values of any two different nodes in the tree.
给出一个二叉排序树和它的头节点,返回树中任意两节点的最小值。

比如:

输入: root = [4,2,6,1,3,null,null]
输出: 1
分析:

给出的树 [4,2,6,1,3,null,null] 代表如下图形:

          4
        /   \
      2      6
     / \
    1   3

最小差值为 1,可能是节点 1 和节点 2 的差值,也可以是节点 3 和 2 的差值。
  1. 节点值在 2 到 100 之间.

  2. 给出的 BST(二叉排序树)一定合法,每一个节点值都是整形,每个节点值都不相同。


能做出来的最简单的方法,但是浪费空间时间,一直在找更优解,欢迎指正。

class Solution {
public:
    vector<int> num;
    int minDiffInBST(TreeNode* root) {
        inOrder(root);
        int minVal = INT_MAX;
        for(int i=1;i<num.size();i++){
            minVal = min(minVal,num[i]-num[i-1]);
        }
        return minVal;
    }
    void inOrder(TreeNode* root) {
        if (!root) return;
        inOrder(root->left);
        num.push_back(root->val);
        inOrder(root->right);
    }
};

本文虽拙,却也系作者劳动,转载还请保留本文链接: http://cyleft.com/?p=527



Have any Question or Comment?

发表评论

电子邮件地址不会被公开。 必填项已用*标注