day-21 代码随想录算法训练营（19）二叉树part07

530.二叉搜索树的最小绝对差

思路一：二叉搜索树的中序遍历必为升序数组，加入数组后计算相邻两个数差值，即可求出最小绝对差

思路二：同样的思路，中序遍历，直接使用指针记录上一个节点，同时更新差值

class Solution {
public:int res=INT_MAX;TreeNode*pre=nullptr;void judge(TreeNode*root){if(root==nullptr) return;judge(root->left);if(pre!=nullptr)res=min(res,root->val-pre->val);pre=root;judge(root->right);}int getMinimumDifference(TreeNode* root) {//思路二：双指针递归，中序遍历，计算两节点之间差值judge(root);return res;}
};

501.二叉搜索树中的众数

思路一：使用map和vector，遍历二叉搜索树用map记录元素出现的次数，一次遍历map求出最大次数，二次遍历map求出等于最大次数的值，加入到vector中思路二：使用指针记录pre前一个元素，当pre元素和当前cur元素相等时，更新count值；当pre元素和当前cur元素不等时，使用count更新最大次数值maxNum；

当count值大于maxNum时，清空数组，把新的元素加入数组；

当count值等于maxNum时，把该元素加入数组

236.二叉树的最近公共祖先

思路一：第一次遍历二叉树使用左0右1来记录p和q的路径，然后找出两个路径的相同值，再使用该相同值去遍历二叉树，最后遍历到的值即为最近公共祖先

思路二：（自底向上）后序遍历，考虑两个指定值的分布情况，使用两个指针保存两个指定值，找到直接返回，找不到返回nullptr

class Solution {
public:TreeNode*judge(TreeNode*root,TreeNode*p,TreeNode*q){if(root==nullptr) return root; if(root==p || root==q) return root;//遍历到值时直接返回TreeNode*left=judge(root->left,p,q);TreeNode*right=judge(root->right,p,q);if(left!=nullptr && right!=nullptr) return root;//指定值分布再两侧if(right!=nullptr) return right;//指定值分布在右侧if(left!=nullptr) return left;//指定值分布在左侧return nullptr;//重点：左右都不存在需返回nullptr}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {//后序遍历return judge(root,p,q);}
};