产品发布网站模板,西宁解封最新通知,阳江网络问政平台回复查询,创造网站需要什么条件前言
思路及算法思维#xff0c;指路 代码随想录。 题目来自 LeetCode。
day 19#xff0c;一个愉快的周日~ day 20#xff0c;一个悲伤的周一~
题目详情
[654] 最大二叉树
题目描述
654 最大二叉树
解题思路
前提#xff1a;构造二叉树 思路#xff1a;寻找根节…前言
思路及算法思维指路 代码随想录。 题目来自 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);
}今日收获
二叉树构造二叉搜索树的特征。
