前言
今日文案：
人生不是一支短短的蜡烛，而是一支暂时由我们拿着的火炬。我们一定要把它燃得十分光明灿烂，然后交给下一代的人们。
-肖伯纳
一、修剪二叉搜索树
解题思路：
class Solution { public: TreeNode* trimBST(TreeNode* root, int low, int high) { if(root==0) //空节点直接返回 { return root; } if(root->val<low) //找到的节点 { root->right=trimBST(root->right,low,high); //因为找到的点是太小了要删除。 return root->right; //往右寻找才能找到可以继续链接的节点 } if(root->val>high) { root->left=trimBST(root->left,low,high); return root->left; } root->left=trimBST(root->left,low,high); root->right=trimBST(root->right,low,high); return root;
二、将有序数组转化为二叉搜索树
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
解题思路：
有序数组构建搜索树，我们关键是找到数组中的中点作为根节点，左边的数组是小的作为左子树，右边的数组是大的，作为右子树，如此递归构建。（一般是前序遍历）
class Solution { public: TreeNode* trasversal(vector<int>nums,int left,int right) { if(left>right) //判断终止条件 { return NULL; } int mid=(left+right)/2; //中点 TreeNode*root=new TreeNode(nums[mid]); //构建新节点 root->left=trasversal(nums,left,mid-1); //遍历，此处要注意传入指针的区间 root->right=trasversal(nums,mid+1,right); return root; } TreeNode* sortedArrayToBST(vector<int>& nums) { TreeNode*root=trasversal(nums,0,nums.size()-1); return root; } };
三、把二叉搜索树转化为累加树
这道题的题目就很难理解了，建议看视频。
class Solution { public: int pre=0; void trasversal(TreeNode*cur) { if(cur==NULL) //遇到空节点就返回 { return ; } trasversal(cur->right); //遍历到右边最大的节点 cur->val=cur->val+pre; //相加 pre=cur->val; //储存上一个节点的值 trasversal(cur->left); } TreeNode* convertBST(TreeNode* root) { trasversal(root); return root; } };
只要找到了最大的节点（右下角），然后再从大往小遍历即可。
总结
构建二叉树最主要是前序遍历和选对传进数组边界条件。
