木又连续日更第96天(96/100)
木又的第140篇leetcode解题报告
二叉树
类型第30篇解题报告
leetcode第530题:二叉搜索树的最小绝对差
https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/
【题目】
给定一个所有节点为非负值的二叉搜索树,求树中任意两节点的差的绝对值的最小值。
示例:
输入:
1
\
3
/
2
输出:
1
【思路】
对于排序好的数组,「任意两节点的差的绝对值的最小值」肯定存在于「所有相邻的两元素之间的差值」。
那么对于二叉排序树,中序遍历即可得到排序数组,在寻找相邻两元素之间的差值,取最小值即可。
【代码】
python版本
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# 中序遍历,得到所有元素
ls = []
self.get_elements(root, ls)
val = sys.maxsize
for i in range(1, len(ls)):
val = min(val, abs(ls[i] - ls[i-1]))
return val
def get_elements(self, node, ls):
if not node:
return
self.get_elements(node.left, ls)
ls.append(node.val)
self.get_elements(node.right, ls)
C++版本
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int getMinimumDifference(TreeNode* root) {
// 中序遍历,得到所有节点值
vector<int> ls;
order_traval(root, ls);
int val = INT_MAX;
for(int i=1; i < ls.size(); i++){
val = min(val, abs(ls[i] - ls[i-1]));
}
return val;
}
void order_traval(TreeNode* node, vector<int>& ls){
if(!node)
return ;
order_traval(node->left, ls);
ls.push_back(node->val);
order_traval(node->right, ls);
}
};