前言
思路及算法思维，指路 代码随想录。
题目来自 LeetCode。
day 19，一个愉快的周日~
day 20，一个悲伤的周一~
题目详情
[654] 最大二叉树
题目描述
654 最大二叉树
解题思路
前提：构造二叉树
思路：寻找根节点，左子树范围、右子树范围递归构造子树。
重点：注意数组的范围，左闭右开。
代码实现
C语言
虚拟头节点
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int maxFun(int *nums, int numsSize, int *max)
{
int maxVal = INT_MIN;
int loc = 0;
for (int i = 0; i < numsSize; i++)
{
if (nums[i] > maxVal)
{
maxVal = nums[i];
loc = i;
}
}
*max = maxVal;
return loc;
}
void addNode(struct TreeNode **root, int *nums, int numsSize)
{
if (numsSize == 0)
{
return ;
}
// 寻找最大值做根节点
int maxVal = 0;
int maxLoc = maxFun(nums, numsSize, &maxVal);
// 保存该值为根节点
*root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
(*root)->val = maxVal;
(*root)->left = NULL;
(*root)->right = NULL;
// 构造左子树
addNode(&((*root)->left), nums, maxLoc);
// 构造右子树
addNode(&((*root)->right), nums + maxLoc + 1, numsSize - maxLoc - 1);
return ;
}
struct TreeNode* constructMaximumBinaryTree(int* nums, int numsSize) {
if (numsSize == 0)
{
return NULL;
}
struct TreeNode *root = NULL;
addNode(&root, nums, numsSize);
return root;
}
[617] 合并二叉树
题目描述
617 合并二叉树
解题思路
前提：合并二叉树
思路：二叉树位置重合时，结点值相加；位置仅有一个时，使用该结点，直接改变父节点的子节点的指针指向。
重点：注意结点不仅为非空的情况。
代码实现
C语言
先序遍历 递归
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
void traversal(struct TreeNode **root1, struct TreeNode *root2)
{
// 结点判空
if (*root1 == NULL)
{
*root1 = root2;
return ;
}
if (root2 == NULL)
{
return ;
}
// 两节点均不为空
(*root1)->val += root2->val;
// 遍历左右子树
traversal(&((*root1)->left), root2->left);
traversal(&((*root1)->right), root2->right);
return ;
}
struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {
traversal(&root1, root2);
return root1;
}
层级遍历 队列
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2) {
// 判空
if (root1 == NULL)
{
return root2;
}
if (root2 == NULL)
{
return root1;
}
// 层级遍历 队列
struct TreeNode *queue[2000];
int idx = 0;
queue[idx++] = root1;
queue[idx++] = root2;
int start = 0;
while (start < idx)
{
struct TreeNode *curNode1 = queue[start++];
struct TreeNode *curNode2 = queue[start++];
curNode1->val += curNode2->val;
// 判断左子树情况
if ((curNode1->left == NULL) && (curNode2->left != NULL))
{
curNode1->left = curNode2->left;
}
else if ((curNode1->left != NULL) && (curNode2->left != NULL))
{
queue[idx++] = curNode1->left;
queue[idx++] = curNode2->left;
}
// 判断右子树情况
if ((curNode1->right == NULL) && (curNode2->right != NULL))
{
curNode1->right = curNode2->right;
}
else if ((curNode1->right != NULL) && (curNode2->right != NULL))
{
queue[idx++] = curNode1->right;
queue[idx++] = curNode2->right;
}
}
return root1;
}
[700] 二叉搜索树中的搜索
题目描述
700 二叉搜索树中的搜索
解题思路
前提：二叉搜索树的搜索
思路：二叉搜索树的结点是有序的，先序序列数组是递增的。
重点：二叉搜索树的特点。
代码实现
C语言
先序遍历 递归
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* searchBST(struct TreeNode* root, int val) {
if (root == NULL)
{
return NULL;
}
if (root->val == val)
{
return root;
}
// 遍历左右子树
struct TreeNode *ans = searchBST(root->left, val);
if (ans == NULL)
{
ans = searchBST(root->right, val);
}
return ans;
}
先序递归，平衡二叉树结点有序特性
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* searchBST(struct TreeNode* root, int val) {
if ((root == NULL) || (root->val == val))
{
return root;
}
if (root->val > val)
{
// 遍历左子树
return searchBST(root->left, val);
}
else
{
// 遍历右子树
return searchBST(root->right, val);
}
}
[98] 验证二叉搜索树
题目描述
98 验证二叉搜索树
解题思路
前提：判断是否为二叉搜索树
思路：根据二叉搜索树的定义，可以递归判断该二叉树是否为二叉搜索树，可以中序遍历该树，看是否为递增数组。
重点：该树为二叉搜索树要求不仅仅是根节点值大于左子结点值、小于右子结点值，而是根节点大于左子树的最底层最右结点值、小于右子树的最底层最左结点值。
代码实现
C语言
中序遍历，遍历后判断递增
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
void traversal(struct TreeNode *root, int *nums, int *numsSize)
{
if (root == NULL)
{
return ;
}
// 中序遍历
// 左
traversal(root->left, nums, numsSize);
// 中
nums[(*numsSize)++] = root->val;
// 右
traversal(root->right, nums, numsSize);
return ;
}
bool isValidBST(struct TreeNode* root) {
int nums[10000];
int numsSize = 0;
traversal(root, nums, &numsSize);
for (int i = 1; i < numsSize; i++)
{
if (nums[i] <= nums[i - 1])
{
return false;
}
}
return true;
}
中序遍历，遍历时判断递增
保存当前遍历的节点的最大值，中序遍历中需要不断判断大于该值。
注意：不能使用全局变量，用例测试时不会重置全局变量。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
bool isValidBSTFun(struct TreeNode* root, long long *maxVal)
{
// 判断空节点或者单节点
if (root == NULL)
{
return true;
}
// 左子树 小于
bool ansLeft = isValidBSTFun(root->left, maxVal);
// 中
if (root->val <= *maxVal)
{
return false;
}
else
{
*maxVal = root->val;
}
// 右子树 大于
bool ansRight = isValidBSTFun(root->right, maxVal);
return ((ansLeft) && (ansRight));
}
bool isValidBST(struct TreeNode* root) {
long long maxVal = LONG_MIN;
return isValidBSTFun(root, &maxVal);
}
今日收获
- 二叉树构造；
- 二叉搜索树的特征。
