530.二叉搜索树的最小绝对差
力扣题目链接(opens new window)
给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
1、二叉搜索树——递归中序: 二叉搜索树中序遍历得到的值序列是递增有序的——然后再遍历一遍，求最大值最小值
-遇到二叉搜索树，优先考虑中序排列
-中序输出到一个int数组里（函数结果输出到数组）
用malloc开辟一个int*空间，存放数组
int size=0
设置函数时：f（int*ans，int* size）——因为需要在函数中修改参数，并且传出，所以需要*
将参数传入函数时f（ans，&size）——对应上述的int*
void f(struct TreeNode* root,int *ans,int *size){if(root==NULL) return;f(root->left,ans,size);ans[(*size)++]=root->val;f(root->right,ans,size);
}int getMinimumDifference(struct TreeNode* root) {int *ans=(int*)malloc(sizeof(int)*10000);int size=0;f(root,ans,&size);int min=INT_MAX;for(int i=1;i<size;i++){if(abs(ans[i]-ans[i-1])<min){min=abs(ans[i]-ans[i-1]);}}return min;}简化——不要再遍历数组，求解差值了——在递归中如何记录前一个节点的指针
需要在递归中记录一些信息：
可以采用全局变量的方法！（但是leetcode好像没办法通过）
——这是因为：
leetcode的判定规则：每道题目你提交之后所用的测试用例共享全局变量，这就说得通了，本地跑的通，是因为本地就一组样例，这个时候在本地运行的时候，每次都初始化全局变量，而提交是在服务器跑的，多组样例一起传参，全局变量只会初始化一次，这就是这题result放在全局变量会错误的原因.
————————————————
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。原文链接：https://blog.csdn.net/qq_42956653/article/details/122792277
int min=INT_MAX;
struct TreeNode *pre=NULL;void f(struct TreeNode*root){if(root==NULL) return;f(root->left);if(pre==NULL){pre=root;}else {min=fmin(min,root->val - pre->val);pre=root;}f(root->right);
}int getMinimumDifference(struct TreeNode* root) {int ans=INT_MAX;f(root);return min;
}
可以等价的把全局变量写成在函数中调用的情况！
main函数里：int x=0；
在调用的时候：f（&x）
设计函数时：f（int *x），函数里都要用*x 代指int
void f(struct TreeNode*root,struct TreeNode** pre,int *min){if(root==NULL) return;f(root->left,pre,min);if(*pre==NULL){*pre=root;}else {int a=root->val - (*pre)->val;*min=fmin(*min,a);*pre=root;}f(root->right,pre,min);
}int getMinimumDifference(struct TreeNode* root) {struct TreeNode* pre=NULL;int min=INT_MAX;f(root,&pre,&min);return min;
}
501.二叉搜索树中的众数
力扣题目链接(opens new window)
给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。
假定 BST 有如下定义：
- 结点左子树中所含结点的值小于等于当前结点的值
- 结点右子树中所含结点的值大于等于当前结点的值
- 左子树和右子树都是二叉搜索树
分析：
1、采用中序遍历——必定是递增的
2、序列中 与上一个数字相同，则count++；不同，则count=1，重新开始计数
**记录上一个元素：可以采用全局变量 或者 增加变量 *pre记录
3、用函数变量*max，记录最大值情况
void dfs(struct TreeNode* root,int*count ,int *pre,int *max,int *list,int *top){if(root==NULL) return;dfs(root->left,count,pre,max,list,top);int x=root->val;if(x==*pre){//延续上一个(*count)++;}else{//读到了第一个元素,or未延续(*count)=1;(*pre)=x;}if((*count) == (*max)){list[(*top)++]=x;}if(*count >*max){*max=*count;*top=0;list[(*top)++]=x;}dfs(root->right,count,pre,max,list,top);
}int* findMode(struct TreeNode* root, int* returnSize) {int count=0;int pre=0;int max=0;int *list=(int *)malloc(sizeof(int)*5000);int top=0;if(root==NULL) return NULL;dfs(root, &count, &pre, &max, list, &top);*returnSize=top;return list;}236. 二叉树的最近公共祖先
力扣题目链接(opens new window)
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
分析：
1、如何测定树的公共祖先：
如果找到一个节点，发现左子树出现结点p，右子树出现节点q，或者 左子树出现结点q，右子树出现节点p，那么该节点就是节点p和q的最近公共祖先。
————判断逻辑是 如果递归遍历遇到q，就将q返回，遇到p 就将p返回，那么如果 左右子树的返回值都不为空，说明此时的中节点，一定是q 和p 的最近祖先。
特殊情况：
p包含q / q包含p
2、怎么从上到下：
后序遍历（左右中）就是天然的回溯过程，从下到上，可以根据左右子树的返回值，来处理中节点的逻辑。
3、是否要返回值
如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。（这种情况就是本文下半部分介绍的113.路径总和ii）
如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。 （这种情况我们在236. 二叉树的最近公共祖先 (opens new window)中介绍）
如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径了就要及时返回。（本题的情况）
代码：
struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {if(root==NULL) return NULL;//空结点——nullif(root==p) return p;//遇到pif(root==q) return q;//遇到qstruct TreeNode*a=lowestCommonAncestor(root->left,p,q);//后序+需要遍历整棵树struct TreeNode*b=lowestCommonAncestor(root->right,p,q);if(a && b) return root;//p q分别在左右两个树else if(a && !b) return a;// pq包含的情况+找到二叉树以上的方法else if(!a && b) return b;return NULL;
}
