leetcode刷题-二叉树08

本文主要是介绍leetcode刷题-二叉树08，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

669. 修剪二叉搜索树

代码随想录文档讲解
LeetCode

思路：

如果当前节点的值小于下边界，继续遍历其右孩子
如果当前节点的值大于上边界，继续遍历其左孩子

伪代码c++：

TreeNode* traversal(root, low, high){if(root==NULL) return NULL;if(root->val < low){	right =  traversal(root->right, low, right);return right;}if(root->val > hig){left = traversal(root->left, low, right);return left;}root->left = traversal(root->left, low, high);root->right = traversal(root->right, low, hight);return root;
}

python代码：

class Solution:def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:if not root:return rootif root.val < low:root.right = self.trimBST(root.right, low, high)return root.rightelif root.val > high:root.left = self.trimBST(root.left, low, high)return root.leftroot.left = self.trimBST(root.left, low, high)root.right = self.trimBST(root.right, low, high)return root

108.将有序数组转换为二叉搜索树

leetcode题目链接
代码随想录文档讲解

思路：

题目要求：平衡二叉树

选取一个中间节点（左区间和右区间节点数量相同，平衡二叉树），将数组分为左区间和右区间，递归遍历左区间和右区间，分别构造子树。

伪代码（C++）：

// 区间的定义，左闭右闭
TreeNode* traversal(vector<int>&nums, left, right){if(left > right) return NULL; //非法区间 return mid = (left + right)/2;TreeNode* root = new TreeNode(nums[mid]);root->left = traversal(nums,left, mid-1);root->right = traversal(nums, mid+1, right);return root;
}
root = traversal(nums, 0, nums.size-1);

python代码：

class Solution:def traversal(self, nums, left, right):if left > right:return Nonemid = left + (right - left) // 2root = TreeNode(nums[mid])root.left = self.traversal(nums, left, mid-1)root.right = self.traversal(nums, mid+1, right)return root def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:return self.traversal(nums, 0, len(nums)-1)

538.把二叉搜索树转换为累加树

leetcode题目链接
代码随想录文档讲解

思路：

二叉搜索树 左中右（中序）遍历得到一个有序数组
这里要倒序遍历，就是右中左

把当前节点与前一个节点的值相加，数组中可用双指针，
这里也可以用 双指针

伪代码（C++）：

int pre=0;
void traversal(TreeNode* cur){if(cur==NULL) return;traversal(cur->right);  // 右cur->val += pre;  /中pre = cur->val;traversal(cur->left);  // 左
}

python代码：

class Solution:def traversal(self, cur):if not cur:returnself.traversal(cur.right)cur.val = cur.val + self.preself.pre = cur.valself.traversal(cur.left)def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:self.pre = 0self.traversal(root)return root

二叉树总结

链接

这篇关于leetcode刷题-二叉树08的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---