LeetCode654. 最大二叉树
题目链接：654. 最大二叉树
初次尝试
和昨天最后一题的思路很像，本质上都是递归构建二叉树。
class Solution {
public:
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
if (nums.size() == 0) return NULL;
int max_index, temp = -1;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > temp) {
temp = nums[i];
max_index = i;
}
}
TreeNode* root = new TreeNode(nums[max_index]);
vector<int> left_nums(nums.begin(), nums.begin() + max_index);
vector<int> right_nums(nums.begin() + max_index + 1, nums.end());
root -> left = constructMaximumBinaryTree(left_nums);
root -> right = constructMaximumBinaryTree(right_nums);
return root;
}
};
看完代码随想录后的想法
思路差不多。
LeetCode617. 合并二叉树
题目链接：617. 合并二叉树
初次尝试
写的比较复杂，思路就是前序递归遍历两个树，对应节点进行合并。
class Solution {
public:
TreeNode* traversal(TreeNode* node1, TreeNode* node2) {
if (node1 == NULL && node2 == NULL) return NULL;
TreeNode* root = new TreeNode();
if (node1 == NULL) {
root -> val = node2 -> val;
root -> left = traversal(NULL, node2 -> left);
root -> right = traversal(NULL, node2 -> right);
}
else if (node2 == NULL) {
root -> val = node1 -> val;
root -> left = traversal(node1 -> left, NULL);
root -> right = traversal(node1 -> right, NULL);
}
else {
root -> val = node1 -> val + node2 -> val;
root -> left = traversal(node1 -> left, node2 -> left);
root -> right = traversal(node1 -> right, node2 -> right);
}
return root;
}
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
return traversal(root1, root2);
}
};
看完代码随想录后的想法
果然想复杂了，其实可以直接利用两个现成的树，没有必要声明新的节点。
class Solution {
public:
TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
if (!root1) return root2;
if (!root2) return root1;
root1 -> val += root2 -> val;
root1 -> left = mergeTrees(root1 -> left, root2 -> left);
root1 -> right = mergeTrees(root1 -> right, root2 -> right);
return root1;
}
};
LeetCode700. 二叉搜索树中的搜索
题目链接：700. 二叉搜索树中的搜索
初次尝试
比较常规的一道二叉树遍历题，一遍ac。
class Solution {
public:
TreeNode* traversal(TreeNode* node, int val) {
if (node == NULL) return NULL;
if (node -> val == val) return node;
TreeNode* left_node = traversal(node -> left, val);
TreeNode* right_node = traversal(node -> right, val);
if (left_node) return left_node;
if (right_node) return right_node;
return NULL;
}
TreeNode* searchBST(TreeNode* root, int val) {
return traversal(root, val);
}
};
看完代码随想录后的想法
上面思路没有利用二叉搜索树的有序性，改进后的代码如下。
class Solution {
public:
TreeNode* traversal(TreeNode* node, int val) {
if (node == NULL || node -> val == val) return node;
if (node -> val > val) return traversal(node -> left, val);
if (node -> val < val) return traversal(node -> right, val);
return NULL;
}
TreeNode* searchBST(TreeNode* root, int val) {
return traversal(root, val);
}
};
LeetCode98. 验证二叉搜索树
题目链接：98. 验证二叉搜索树
初次尝试
陷入了陷阱：
- 陷阱1
不能单纯的比较左节点小于中间节点，右节点大于中间节点就完事了。
这是因为二叉搜索树的定义为：
假设一个二叉搜索树具有如下特征：
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
注意是节点整个左子树的所有值都要小于当前节点值，而不仅仅是左子节点一个节点。
看完代码随想录后的想法
要知道中序遍历下，输出的二叉搜索树节点的数值是有序序列。
有了这个特性，验证二叉搜索树，就相当于变成了判断一个序列是不是递增的了。
所以可以中序递归遍历，判断节点值是否递增，要注意样例中最小节点可能是int的最小值，如果这样使用最小的int来比较也是不行的。
此时可以初始化比较元素为longlong的最小值。
class Solution {
public:
long long max_val = LONG_MIN;
bool isValidBST(TreeNode* root) {
if (!root) return true;
bool left = isValidBST(root -> left);
if (root -> val > max_val) max_val = root -> val;
else return false;
bool right = isValidBST(root -> right);
return left && right;
}
};