给定一个不重复的整数数组 nums
。 最大二叉树 可以用下面的算法从 nums
递归地构建:
nums
中的最大值。返回 nums
构建的 *最大二叉树* 。
示例 1:
输入:nums = [3,2,1,6,0,5]
输出:[6,3,5,null,2,0,null,null,1]
解释:递归调用如下所示:
- [3,2,1,6,0,5] 中的最大值是 6 ,左边部分是 [3,2,1] ,右边部分是 [0,5] 。
- [3,2,1] 中的最大值是 3 ,左边部分是 [] ,右边部分是 [2,1] 。
- 空数组,无子节点。
- [2,1] 中的最大值是 2 ,左边部分是 [] ,右边部分是 [1] 。
- 空数组,无子节点。
- 只有一个元素,所以子节点是一个值为 1 的节点。
- [0,5] 中的最大值是 5 ,左边部分是 [0] ,右边部分是 [] 。
- 只有一个元素,所以子节点是一个值为 0 的节点。
- 空数组,无子节点。
示例 2:
输入:nums = [3,2,1]
输出:[3,null,2,null,1]
提示:
1 <= nums.length <= 1000
0 <= nums[i] <= 1000
nums
中的所有整数 互不相同/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode * traversal(vector<int> & nums, int left, int right) {
if (left >= right){
return nullptr;
}
// 寻找分割点
int maxIndex = left;
for (int i = maxIndex + 1; i < right; i++) {
if (nums[i] > nums[maxIndex]){
maxIndex = i;
}
}
// 根节点
TreeNode * node = new TreeNode(nums[maxIndex]);
// 连接
node->left = traversal(nums, left, maxIndex);
node->right = traversal(nums, maxIndex+1, right);
return node;
}
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
return traversal(nums, 0, nums.size());
}
};
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def traversal(self, nums, left, right):
if left >= right:
return None
maxIndex = left
for i in range(left+1, right):
if nums[i] > nums[maxIndex]:
maxIndex = i
node = TreeNode(nums[maxIndex])
node.left = self.traversal(nums, left, maxIndex)
node.right = self.traversal(nums, maxIndex+1, right)
return node
def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
return self.traversal(nums, 0, len(nums))
给你两棵二叉树: root1
和 root2
。
想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。
返回合并后的二叉树。
注意: 合并过程必须从两个树的根节点开始。
示例 1:
输入:root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出:[3,4,5,5,4,null,7]
示例 2:
输入:root1 = [1], root2 = [1,2]
输出:[2,2]
提示:
[0, 2000]
内-104 <= Node.val <= 104
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* traversal(TreeNode* r1, TreeNode* r2) {
// 如果r1为空了,则返回r2
if (r1 == nullptr) return r2;
if (r2 == nullptr) return r1;
r1->val += r2->val;
r1->left = traversal(r1->left, r2->left);
r1->right = traversal(r1->right, r2->right);
return r1;
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
return traversal(root1, root2);
}
};
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
if not root1:
return root2
if not root2:
return root1
root1.val += root2.val
root1.left = self.mergeTrees(root1.left, root2.left)
root1.right = self.mergeTrees(root1.right, root2.right)
return root1
给定二叉搜索树(BST)的根节点 root
和一个整数值 val
。
你需要在 BST 中找到节点值等于 val
的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null
。
示例 1:
输入:root = [4,2,7,1,3], val = 2
输出:[2,1,3]
示例 2:
输入:root = [4,2,7,1,3], val = 5
输出:[]
提示:
[1, 5000]
范围内1 <= Node.val <= 107
root
是二叉搜索树1 <= val <= 107
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* traversal(TreeNode * root, int val) {
if (root == nullptr) {
return nullptr;
}
if (root->val == val) {
return root;
}
TreeNode * result = nullptr;
// 二叉搜索树有序的,
if (root->val > val) {
result = traversal(root->left, val);
}
if (root->val < val) {
result = traversal(root->right, val);
}
return result;
}
TreeNode* searchBST(TreeNode* root, int val) {
return traversal(root, val);
}
};
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
if not root:
return None
if root.val == val:
return root
result = None
if root.val > val:
result = self.searchBST(root.left, val)
if root.val < val:
result = self.searchBST(root.right, val)
return result
给你一个二叉树的根节点 root
,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
示例 1:
输入:root = [2,1,3]
输出:true
示例 2:
输入:root = [5,1,4,null,null,3,6]
输出:false
解释:根节点的值是 5 ,但是右子节点的值是 4 。
提示:
[1, 104]
内-231 <= Node.val <= 231 - 1
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> vec;
// 中序遍历
void traversal(TreeNode* node) {
if (node == nullptr) {
return;
}
traversal(node->left);
vec.push_back(node->val);
traversal(node->right);
}
bool isValidBST(TreeNode* root) {
traversal(root);
for (int i = 1; i < vec.size(); i++) {
if (vec[i] < vec[i-1]) {
return false;
}
}
return true;
}
};
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def __init__(self):
self.res = []
def traversal(self, root):
if not root:
return None
self.traversal(root.left)
self.res.append(root.val)
self.traversal(root.right)
def isValidBST(self, root: Optional[TreeNode]) -> bool:
self.traversal(root)
for i in range(1, len(self.res)):
if (self.res[i] <= self.res[i-1]):
return False
return True