dedecms网站备份,网站开发具体工作有那些,wordpress 必须登录,西宁网站建设报价这道题需要在递归的同时使用双指针。先找到一个区间的中间值#xff0c;当作子树的父节点#xff0c;再递归该中间值的左区间和右区间#xff0c;用于生成该父节点的左子树和右子树。这就是此题的递归逻辑。而双指针就体现在每一层递归都要使用左指针和右指针来找到中间值。…这道题需要在递归的同时使用双指针。先找到一个区间的中间值当作子树的父节点再递归该中间值的左区间和右区间用于生成该父节点的左子树和右子树。这就是此题的递归逻辑。而双指针就体现在每一层递归都要使用左指针和右指针来找到中间值。这里的双指针的移动逻辑与二分法中双指针的移动相同。所以我们也需要注意合法区间的选择。如果对二分法不熟悉的同学可以看我这篇文章二分查找注意事项-CSDN博客。另外这道题的递归函数的返回值为指向节点的指针从而可以使用链表的连接操作将生成的父节点与上一层的父节点连接最终构造成一棵树。大家可以结合我下面的代码及注释理解此题。
代码及注释如下
/*** 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* travel(vectorint nums,int left,int right){//终止条件我们事先规定合法区间为左闭右闭则当左指针大于右指针时终止递归if(left right) return NULL;//每递归到下一层就生成新节点int mid (left right) / 2;//通过双指针二分可以保证该二叉树为平衡二叉树TreeNode* newNode new TreeNode(nums[mid]);//将递归函数返回的节点与当前节点连接从而形成树newNode - left travel(nums,left,mid - 1);newNode - right travel(nums,mid 1,right);//返回当前子树父节点给上一层最终可以返回平衡二叉树根节点return newNode;}TreeNode* sortedArrayToBST(vectorint nums) {return travel(nums,0,nums.size() - 1);}
};
