{"id":1796,"date":"2018-02-10T22:01:13","date_gmt":"2018-02-11T06:01:13","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=1796"},"modified":"2018-02-11T14:06:59","modified_gmt":"2018-02-11T22:06:59","slug":"leetcode-783-minimum-distance-between-bst-nodes","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-783-minimum-distance-between-bst-nodes\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 783. Minimum Distance Between BST Nodes"},"content":{"rendered":"
\n
\n

Given a Binary Search Tree (BST) with the root node\u00a0root<\/code>, return\u00a0the minimum difference between the values of any two different nodes in the tree.<\/p>\n

Example :<\/strong><\/p>\n

Input: root = [4,2,6,1,3,null,null]\r\nOutput: 1\r\nExplanation:\r\nNote that root is a TreeNode object, not an array.\r\n\r\nThe given tree [4,2,6,1,3,null,null] is represented by the following diagram:\r\n\r\n          4\r\n        \/   \\\r\n      2      6\r\n     \/ \\    \r\n    1   3  \r\n\r\nwhile the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.\r\n<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. The size of the BST will be between 2 and\u00a0100<\/code>.<\/li>\n
  2. The BST is always valid, each node’s value is an integer, and each node’s value is different.<\/li>\n<\/ol>\n<\/div>\n<\/div>\n
    Solution 1: In order traversal\u00a0<\/b><\/p>\n
    Time complexity: O(n)<\/p>\n
    Space complexity: O(n)<\/p>\n
    C++<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 783\r\nclass Solution {\r\npublic:\r\n  int minDiffInBST(TreeNode* root) {\r\n    min_diff_ = INT_MAX;\r\n    prev_ = nullptr;\r\n    minDiff(root);\r\n    return min_diff_;\r\n  }\r\nprivate:\r\n  int min_diff_;\r\n  int* prev_;\r\n  void minDiff(TreeNode* root) {\r\n    if (root == nullptr) return;    \r\n    minDiff(root->left);\r\n    if (prev_ != nullptr)\r\n      min_diff_ = min(min_diff_, abs(root->val - *prev_));\r\n    prev_ = &root->val;\r\n    minDiff(root->right);\r\n  }\r\n};<\/pre>\n
    Related Problems:<\/strong><\/p>\n