公司内部网站模板,展厅宣传片,wordpress文章分类,手机制作报价单app一、思路
递归
二、解题方法
在给定中序遍历序列数组的情况下#xff0c;每一个子树中的数字在数组中一定是连续的#xff0c;因此可以通过数组下标范围确定子树包含的数字#xff0c;下标范围记为 [left,right]。对于整个中序遍历序列#xff0c;下标范围从 left0到 ri… 一、思路
递归
二、解题方法
在给定中序遍历序列数组的情况下每一个子树中的数字在数组中一定是连续的因此可以通过数组下标范围确定子树包含的数字下标范围记为 [left,right]。对于整个中序遍历序列下标范围从 left0到 rightnums.size()−1。当 leftright 时平衡二叉搜索树为空。
选择中间位置左边的数字作为根节点
三、code
class Solution {
public:TreeNode* sortedArrayToBST(vectorint nums) {return helper(nums,0,nums.size()-1);}TreeNode* helper(vectorint nums,int left,int right){if(leftright)//当左边界 left 大于右边界 right 时意味着当前处理的区间为空即没有元素可以用来构建子树了。这种情况下我们返回 nullptr表示当前子树为空树。{return nullptr;}int mid(leftright1)/2;//计算当前处理区间的中间位置总是选择中间位置左边的数字作为根节点。这样可以保证构建的二叉搜索树是高度平衡的。TreeNode* rootnew TreeNode(nums[mid]);//创建当前区间中间位置的元素值为根节点的二叉树节点。root-lefthelper(nums,left,mid-1);//递归构建当前根节点的左子树将左边界设为 left右边界设为中间位置的前一个位置 mid - 1。root-righthelper(nums,mid1,right);//递归构建当前根节点的右子树将左边界设为中间位置的后一个位置 mid 1右边界设为 right。return root;}
}; 学到的知识
①
前序遍历Preorder Traversal在二叉树中先访问根节点然后按照左子树、右子树的顺序递归遍历子树。在前序遍历中根节点的访问顺序是最先的。
中序遍历Inorder Traversal在二叉树中先按照左子树、根节点、右子树的顺序递归遍历子树。在中序遍历中根节点的访问顺序位于左右子树之间。
后序遍历Postorder Traversal在二叉树中先按照左子树、右子树、根节点的顺序递归遍历子树。在后序遍历中根节点的访问顺序是最后的。
这三种遍历方式是深度优先搜索DFS的三种不同变种。它们分别有不同的应用场景
前序遍历适用于需要先处理根节点再处理子节点的场景比如复制整个树的结构或序列化为字符串。中序遍历适用于二叉搜索树可以将其按从小到大的顺序输出比如查找树中第 k 小的元素。后序遍历适用于释放二叉树的内存先释放子节点再释放根节点以防止访问已经释放的内存。
②TreeNode* root new TreeNode(nums[mid]);
这行代码用于创建一个新的二叉树节点并将其值初始化为有序数组中间位置的元素 nums[mid]
