【算法日志】二叉树：二叉树的修剪、构建和遍历以及二叉树总结(day20)_二叉树剪枝遍历顺序

代码随想录刷题60Day

---

目录

前言

二叉树的修剪

数组构建BST

BST转累加树

二叉树的简结

---

前言

本日还是对二叉树的一些刷题。由于今日是二叉树章节的最后一天，会适当的做一些总结，算是这些天的收获吧。

---

二叉树的修剪

本题主要的坑点是单调递增的数据在二叉搜索树中并不是节点连节点连续分布的，因此某个节点不在有效数据范围中时，不能直接将其连同其子树一同剪掉，其子树也可能有符合数据范围的节点。

解决该问题有两种方法，一是使用前序遍历自上而下寻找处在数据边界的节点。如果是在数据的左界，则在边界节点的右树寻找有效数据；在右界则在边界节点的左树寻找有效数据。至于怎样在边界节点的子树寻找有效数据，则会用到分治思想。

还有一种是使用后序遍历，自下而上从新构树，这种方法相较于第一种方法，理解上要容易许多。

以下是两种方法的示例代码 

	TreeNode* in_trimBST(TreeNode* root, int low, int high)
	{
		//含有两处的双递归逻辑比较隐晦，需重点去理解这一过程。
		if (root == nullptr)return nullptr;
		if (root->val < low)
		//如果root值小于low，则其节点和其左树节点都会被舍弃，这里的root
		//既指root根节点，也指root左树中的某一根节点（既包括初始状态，
		//也包括在递归中的某一子根节点的状态）
			return in_trimBST(root->right, low, high);
		//这里还要去寻找该节点右树是否还存在区间内的值
		if (root->val > high)//
			return in_trimBST(root->left, low, high);
		//这里时递去操作
		root->left = in_trimBST(root->left, low, high);
		root->right = in_trimBST(root->right, low, high); 
		return root;
	}
 
	TreeNode* pre_trimBST(TreeNode* root, int low, int high)
	{
		if (root == nullptr)return nullptr;
		root->left = pre_trimBST(root->left, low, high);
		root->right = pre_trimBST(root->right, low, high);
		if (root->val < low || root->val > high)
		{
			if (root->left)
				return root->left;
			if (root->right)
				return root->right;
			return nullptr;
		}
		return root;
	}

数组构建BST

	TreeNode* arrayBuildTree(vector<int>& nums, int left, int right)
	{
		if (left == right)return nullptr;
		int middle = (left & right) + ((left ^ right) >> 1);
		TreeNode* root = new TreeNode(nums[middle]);
		root->left = arrayBuildTree(nums, left, middle);
		root->right = arrayBuildTree(nums, middle + 1, right);
		return root;
	}
	TreeNode* sortedArrayToBST(vector<int>& nums)
	{
		return arrayBuildTree(nums, 0, nums.size());
	}

BST转累加树

	TreeNode* prenode = nullptr;
	TreeNode* convertBST(TreeNode* root)
	{
		if (root == nullptr)return root;
		//这里返回值其实作用不大，赋值可有可无
		root->right = convertBST(root->right);
		if (prenode)root->val += prenode->val;
		prenode = root;
		root->left = convertBST(root->left);
		return root;
	}

---

二叉树的简结

二叉树作为一种十分重要的数据结构，我们应熟练掌握其构建方法，增删操作以及遍历方式。

其中遍历方式又分前序遍历，中序遍历和后序遍历，很多关于二叉树的问题围绕其遍历方式来解决的。

同时，分治思想在二叉树中也很常见，很多复杂的二叉树问题都可以分治成一个个树节点问题。总而言之，多思考多总结，很多二叉树问题也没想象地那么难解决。