前言
今日文案：
铤而走险，奔驰不已。血溅于渊兮水流如雨。
一、二叉搜索树的最小绝对差
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
class Solution { public: int ans=INT_MAX; TreeNode*pre=nullptr; //初始化 void search(TreeNode*cur) { if(cur==NULL) //终止条件 { return; } search(cur->left); //中序遍历 if(pre!=nullptr) //第一次进入，cur还在叶子节点就不用判断 { ans=min(ans,cur->val-pre->val); //记录最小值，cur->val是一定大于pre->val } pre=cur; //快慢指针 search(cur->right); } int getMinimumDifference(TreeNode* root) { search(root); return ans; } };
这里主要是运用了快慢指针去遍历整个二叉搜索树，寻找最小值。
二、二叉搜索树中的众数
class Solution { public: int count=1,maxcount=0; //记录数字出现重复的频率 TreeNode*pre=0; //双指针 vector<int> ans; void traversal(TreeNode*root) { if(root==0) //终止条件 { return ; } traversal(root->left); //中序遍历 if(pre!=0&&pre->val==root->val) //双指针，后一个的值等于前一个频率加1 { count++; } else //如果不等，说明断开了，重置1 { count=1; } pre=root; //跟上快指针 if(count==maxcount) //储存众数 { ans.push_back(root->val); } if(count>maxcount) //出现了更高频率的 { maxcount=count; //重置最大频率 ans.clear(); //清除原来的答案，因为跟不上最大频率 ans.push_back(root->val); //插进新的众数 } traversal(root->right); //遍历 return ; } vector<int> findMode(TreeNode* root) { traversal(root); return ans; } };
三、二叉树的最近公共祖先
class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if(root==0) //遍历到空节点，返回空 { return NULL; } if(root==p||root==q) //遇到其中一个就返回节点 { return root; } TreeNode*left=lowestCommonAncestor(root->left,p,q); //后序遍历，先处理子树再返中 TreeNode*right=lowestCommonAncestor(root->right,p,q); if(left!=0&&right!=0) //分析各种情况 { return root; } if(left==NULL&&right!=NULL) //只有一个记录就继续返回给上一层 { return right; } if(left!=NULL&&right==NULL) { return left; } else { return NULL; } } };
总结
写到这里，我觉得对于二叉树的遍历才是最主要的，主要是要分清怎么遍历，再加上每道题的特点，条件判断，杀穿二叉树！！1
