算法训练day21 LeetCode 530.501.236
530二叉搜索树的最小绝对差
题目
题解
-
中序遍历二叉平衡树 --> 有序数组 --> 遍历数组得到最小绝对差
-
class Solution { private: vector<int> vec; void traversal(TreeNode* root) { if(root==NULL) return; traversal(root->left); vec.push_back(root->val); traversal(root->right); } public: int getMinimumDifference(TreeNode* root) { vec.clear(); traversal(root); if(vec.size()<2) return 0; int minValue = INT_MAX; for(int i=1;i<vec.size();i++) { minValue=min(minValue,vec[i]-vec[i-1]); } return minValue; } };
-
不转换成数组,使用双指针
-
class Solution { private: int result = INT_MAX; TreeNode *pre = NULL; void traversal(TreeNode *cur) { if (cur == NULL) return; traversal(cur->left); if (pre != NULL) { result = min(result, cur->val - pre->val); } pre = cur; traversal(cur->right); } public: int getMinimumDifference(TreeNode *root) { traversal(root); return result; } };
501.二叉搜索树中的众数
题目
题解
-
因为二叉搜索树采用中序遍历结果是递增的 --> 比较相邻的元素是否相同
-
可以将树转换成数组
-
也直接在平衡树中中序遍历
-
class Solution { private: int maxCount = 0; int count = 0; TreeNode *pre = NULL; vector<int> result; void searchBST(TreeNode *cur) { if (cur == NULL) return; searchBST(cur->left); if (pre == NULL) { count = 1; } else if (pre->val == cur->val) { count++; } else { count = 1; } pre = cur; if (count == maxCount) { result.push_back(cur->val); } if (count > maxCount) { maxCount = count; result.clear(); result.push_back(cur->val); } searchBST(cur->right); return; } public: vector<int> findMode(TreeNode *root) { count = 0; maxCount = 0; pre = NULL; result.clear(); searchBST(root); return result; } };
-
一直忽略了二叉平衡树的顺序性----顺序意味着相同的值一定相邻----双指针的使用非常巧妙
-
236. 二叉树的最近公共祖先
题目
题解
-
先遍历树,找到一个节点 ----- 后从该节点最近父节点开始向下遍历 ----- 找不到则继续向上回溯再遍历
-
递归地,如果找到了目标节点就返回指针,否则返回空值 ----- 那么一个节点处接收到的均为两个指针则该节点为最近公共祖先
-
class Solution { public: TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) { if (root == q || root == p || root == NULL) return root; TreeNode *left = lowestCommonAncestor(root->left, p, q); TreeNode *right = lowestCommonAncestor(root->right, p, q); if (left != NULL && right != NULL) return root; if (left == NULL && right != NULL) return right; else if (left != NULL && right == NULL) return left; else { return NULL; } } };