为二叉搜索树

本题需要注意的点很多不能够轻易的就把节点删除首先1.本题给出的最小边界值和最大边界值不一定会存在树中只是提供一个区间大小因此不能够节点判断是否等于low或者high。

2.在找到小于low的值后不能够直接将其删除因为它的右孩子不一定小于low同理大于high的节点也不能直接删除还需要关注它的左孩子。

3.在2的基础上也不能直接把右孩子返回因为右孩子大于low的情况下右孩子的左孩子还是可能会小于low需要删除因此还需要不断的进行遍历。

该情况如下图所示如果区间在[2,3]之间

//时间复杂度O(n)

public://确定返回值本题需要重新构造二叉树节点因此使用返回值更加方便当然也可以没有返回值就需要手动进行左右孩子构造TreeNode*

trimBST(TreeNode*

nullptr;//确定单层递归逻辑核心是将root转移到low和high区间内//1.当前值大于highif

(root-val

high);}//3.当前值在low和high区间内但是还不能就此下定义还需要判断该节点左右孩子是否合格root-left

trimBST(root-left,

代码本题也能够使用迭代法且由于二叉搜索树自带遍历条件因此不需要额外空间。

//时间复杂度O(n)

注意本题需要构造的不仅是二叉搜索树还需要是一颗平衡二叉树。

平衡二叉树需要所有中间节点的左右孩子的高度差不大于1。

依据上述条件又因为本题给的数组已经是一个升序排列的数组了因此本题显然是从中间节点进行构造每次取数组的中间节点即可构造出平衡的二叉搜索树。

注意如果数组是奇数显然选中间的节点如果数组是偶数则中间的两个节点选哪个都可以只要统一就行最后构造出的二叉树会有所区别这也是本题答案不唯一的原因。

//时间复杂度O(n)

TreeNode(nums[mid]);//左区间vectorint

left(nums.begin(),

sortedArrayToBST(left);node-right

node;}

TreeNode(nums[mid]);//左区间node-left

traversal(nums,

学习本题最重要的是需要找到它的规律本题是将每个节点的新值转变为等于原树中大于或等于node.val的值之和。

如果将二叉搜索树通过中序遍历转化为数组来看的话其实就是从后往前依次累加。

因此本题应该采用的遍历方法是反中序遍历通过右中左的遍历顺序因此将节点值累加。

注意本题累加过程中采用的是双指针的方法需要一个指向当前节点的前一个节点pre来保存上一个节点的累加和。

//时间复杂度O(n)

//指向当前节点的前一个节点//本题不需要返回值只用将当前值改变就行void

traversal(TreeNode*

return;//本题的遍历顺序应该为右中左//右traversal(root-right);//中if(pre

nullptr)

root;//左traversal(root-left);}TreeNode*

convertBST(TreeNode*

对于二叉树来说我们首先需要掌握的就是递归这一算法确定递归三部曲掌握通过递归进行的二叉树的前序遍历、中序遍历、后序遍历的方法。

其次对于二叉树来说它的迭代方法同样也很重要递归由于其不断递归的特殊性稍有不慎就容易导致栈溢出且问题相对于迭代法不好排查。

因此掌握迭代法对于实际工程使用也十分重要。

这七天我们对二叉树的遍历方式各种属性二叉树的修改和构造都进行了详细的练习。

并且对二叉树中一个重要的类型二叉搜索树也进行了详细的考察二叉搜索树自带的遍历顺序能够便于解答很多问题同时对二叉搜索树进行中序遍历能够得到一个非递减序列也是重要的性质之一。

总结来说

涉及到二叉树的构造无论普通二叉树还是二叉搜索树一定都是先构造中节点。

求普通二叉树的属性一般是后序一般要通过递归函数的返回值做计算。

包括是否对称求最大深度最小深度有多少个节点是否平衡路径问题左叶子之和、左下角的值等