二叉树的先序。给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。
提示: + 树中至少有 2 个节点。 + 本题与783相同
中序、题目链接
输入:13/2输出:
1
给定的树是二叉搜索树,使用中序遍历二叉搜索树,会得到一个递增的序列。
因此,两节点差绝对值的最小值必然出现在递增序列的两个连续数字中。
二叉树的中序遍历:
void InOrder(tree root){if (root == NULL) return ;InOrder(root->left);visit(root->val);InOrder(root->right);
}
我们自然可以通过中序遍历,将每次遍历的结果储存在数组中,再求数组相邻元素的差绝对值的最小值。也可以不借助数组,通过储存每一次差的绝对值temp
,与当前最小值比较min
,如果temp < min
,令min = temp
。
如果前者代码易懂,后者空间消耗很小。
class Solution {
public:int flag = 0;int cur;int pre;void InOrder(TreeNode* root,int &temp, int &min){if (root == NULL) return ;InOrder(root->left, temp, min);if (flag == 0){flag = 1;pre = root->val;}else {cur = root->val;temp = abs(pre - cur);if (temp < min){min = temp;}pre = cur;}InOrder(root->right, temp, min);}int getMinimumDifference(TreeNode* root) {if (root == NULL) return 0;int temp;if (root->left == NULL){temp = abs(root->val - root->right->val);}else{temp = abs(root->val - root->left->val);}int min = temp;InOrder(root, temp, min);return min;}
};
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态