二叉树的先序,怎样将树的中序遍历的数输入到一个数组中_LeetCode 530.二叉搜索树的最小绝对差

 2023-09-23 阅读 20 评论 0

摘要:题目二叉树的先序。给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。提示: + 树中至少有 2 个节点。 + 本题与783相同中序、题目链接示例输入:13/2输出: 1题目分析给定的树是二叉搜索树,使用中序遍历

e28d68d099746ea058384c238a4cd2ec.png

题目

二叉树的先序。给你一棵所有节点为非负值的二叉搜索树,请你计算树中任意两节点的差的绝对值的最小值。

提示: + 树中至少有 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;}
};

版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。

原文链接:https://hbdhgg.com/5/91628.html

发表评论:

本站为非赢利网站,部分文章来源或改编自互联网及其他公众平台,主要目的在于分享信息,版权归原作者所有,内容仅供读者参考,如有侵权请联系我们删除!

Copyright © 2022 匯編語言學習筆記 Inc. 保留所有权利。

底部版权信息