网站 备案网站,网页制作排行榜,网站建设的要求,苏州建设工程交易中心网站这道题还是比较复杂#xff0c;在递归上与之前写过的二叉树的题目都有所不同。如果当前递归到的子树的父节点不在范围中#xff0c;我们根据节点数值的大小选择进行左递归还是右递归。为什么找到了不满足要求的节点之后#xff0c;还要进行递归呢#xff1f;因为该不满足要…这道题还是比较复杂在递归上与之前写过的二叉树的题目都有所不同。如果当前递归到的子树的父节点不在范围中我们根据节点数值的大小选择进行左递归还是右递归。为什么找到了不满足要求的节点之后还要进行递归呢因为该不满足要求的父节点的子树中可能存在满足要求的节点我们要不断递归子树寻找这些满足要求的节点并向上返回直到遇到空节点为止。注意这里递归函数的返回值为指向节点的指针用来返回满足要求的节点。另外递归到的子树的父节点满足要求时需要进行链表的连接操作刚好接住前面所说的满足要求的节点最后再向上返回该节点用于之后的连接。大家可以结合我下面的代码及注释理解此题。
代码及注释如下
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* trimBST(TreeNode* root, int low, int high) {//终止条件if(root NULL){return NULL;}//如果节点值不在范围中则根据节点值的大小选择进行左递归还是右递归if(root - val low){//这里的递归是为了找到满足要求的子树父节点TreeNode* right trimBST(root - right,low,high);//返回该子树父节点return right;}if(root - val high){//这里的递归是为了找到满足要求的子树父节点TreeNode* left trimBST(root - left,low,high);//返回该子树父节点return left;}//如果当前节点在范围中则将当前节点与子树父节点连接TreeNode* a trimBST(root - left,low,high);TreeNode* b trimBST(root - right,low,high);root - left a;root - right b;//返回连接后的新子树父节点return root;}
};
