网站建设目录结构doc,wordpress导航网站,wordpress4.9火车头发布模板,子网站 两微一端的建设方案文章目录1.预备知识1.1 二叉树定义1.2 二叉树的构造2.路径总和 II2.1 题目描述2.2 算法思路2.3 C实现3.二叉树的最近公共祖先3.1 题目描述3.2 解题思路3.3 C实现4.二叉树展开为链表4.1 题目描述4.2 思考4.3 C实现4.4 解法二4.5 C实现5.二叉树的右视图5.1 预备知识5.2 题目描述5…
文章目录1.预备知识1.1 二叉树定义1.2 二叉树的构造2.路径总和 II2.1 题目描述2.2 算法思路2.3 C实现3.二叉树的最近公共祖先3.1 题目描述3.2 解题思路3.3 C实现4.二叉树展开为链表4.1 题目描述4.2 思考4.3 C实现4.4 解法二4.5 C实现5.二叉树的右视图5.1 预备知识5.2 题目描述5.3 解题思路5.4 C实现6. 课程表6.1 预备知识6.1.1 什么是图6.1.2 图的表示6.1.3 图的深度优先遍历6.1.4 图的宽度优先遍历6.2 题目描述6.3 分析6.4 C代码实现1.预备知识
1.1 二叉树定义 1.2 二叉树的构造 2.路径总和 II
2.1 题目描述 给你二叉树的根节点 root 和一个整数目标和 targetSum 找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 2.2 算法思路 2.3 C实现
/*** 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:vectorvectorint pathSum(TreeNode* root, int targetSum) {vectorvectorint result;vectorint path;int path_value0;preorder(root,path_value,targetSum,path,result);return result;}
private:void preorder(TreeNode* Node,int path_value,int sum,vectorint path,vectorvectorint result){if(!Node){return;}path_valueNode-val;path.push_back(Node-val);if(path_valuesumNode-leftnullptrNode-rightnullptr){result.push_back(path);}preorder(Node-left,path_value,sum,path,result);preorder(Node-right,path_value,sum,path,result);path_value-Node-val;path.pop_back();}
};3.二叉树的最近公共祖先
3.1 题目描述 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为“对于有根树 T 的两个节点 p、q最近公共祖先表示为一个节点 x满足 x 是 p、q 的祖先且 x 的深度尽可能大一个节点也可以是它自己的祖先。” 3.2 解题思路 3.3 C实现
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {vectorTreeNode* path;vectorTreeNode* node_p_path;vectorTreeNode* node_q_path;int finish0;preorder(root,p,path,node_p_path,finish);path.clear();finish0;preorder(root,q,path,node_q_path,finish);int path_length0;if(node_p_path.size()node_q_path.size()){path_lengthnode_p_path.size();}else{path_lengthnode_q_path.size();}TreeNode* result0;for(int i0;ipath_length;i){if(node_p_path[i]node_q_path[i]){resultnode_p_path[i];}}return result;}private:void preorder(TreeNode* Node,TreeNode* search,vectorTreeNode* path,vectorTreeNode* result,int finish){if(!Node||finish1){return;}path.push_back(Node);if(Nodesearch){finish1;resultpath;}preorder(Node-left,search,path,result,finish);preorder(Node-right,search,path,result,finish);path.pop_back();}
};4.二叉树展开为链表
4.1 题目描述 给你二叉树的根结点 root 请你将它展开为一个单链表 展开后的单链表应该同样使用 TreeNode 其中 right 子指针指向链表中下一个结点而左子指针始终为 null 。 展开后的单链表应该与二叉树 先序遍历 顺序相同。 4.2 思考 4.3 C实现
/*** 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:void flatten(TreeNode* root) {vectorTreeNode* node_vec;preorder(root,node_vec);for(int i1;inode_vec.size();i){node_vec[i-1]-leftnullptr;node_vec[i-1]-rightnode_vec[i];}}
private:void preorder(TreeNode* Node,vectorTreeNode* node_vec){if(!Node){return;}node_vec.push_back(Node);preorder(Node-left,node_vec);preorder(Node-right,node_vec);}
};
4.4 解法二 4.5 C实现
/*** 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:void flatten(TreeNode* root) {TreeNode* lastnullptr;preorder(root,last);}private:void preorder(TreeNode* Node,TreeNode* last){if(!Node){return;}if(!Node-left!Node-right){lastNode;return;}TreeNode* leftNode-left;TreeNode* rightNode-right;TreeNode* left_lastnullptr;TreeNode* right_lastnullptr;if(left){preorder(left,left_last);Node-leftnullptr;Node-rightleft;lastleft_last;}if(right){preorder(right,right_last);if(left_last){left_last-rightright;}lastright_last;}}
};5.二叉树的右视图
5.1 预备知识 #include iostream
#includequeue
using namespace std;struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x):val(x),left(NULL),right(NULL){}
};
void BFS_print(TreeNode* root) {queueTreeNode* Q;Q.push(root);while (Q.size()) {TreeNode* node Q.front();Q.pop();cout node-val endl;if (node-left) {Q.push(node-left);}if (node-right) {Q.push(node-right);}}
}
int main()
{TreeNode tree1(1);TreeNode tree2(11);TreeNode tree3(9);TreeNode tree4(3);TreeNode tree5(0);TreeNode tree6(2);TreeNode tree7(8);tree1.left tree2;tree1.right tree3;tree2.left tree4;tree2.right tree5;tree3.left tree6;tree3.right tree7;BFS_print(tree1);return 0;
}5.2 题目描述 给定一棵二叉树想象自己站在它的右侧按照从顶部到底部的顺序返回从右侧所能看到的节点值。 5.3 解题思路 5.4 C实现
/*** 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:vectorint rightSideView(TreeNode* root) {vectorint view;queuepairTreeNode*,int Q;if(root){Q.push(make_pair(root,0));}while(!Q.empty()){TreeNode *nodeQ.front().first;int depthQ.front().second;Q.pop();if(depthview.size()){view.push_back(node-val);}else{view[depth]node-val;}if(node-left){Q.push(make_pair(node-left,depth1));}if(node-right){Q.push(make_pair(node-right,depth1));}}return view;}
};6. 课程表
6.1 预备知识
6.1.1 什么是图 6.1.2 图的表示 6.1.3 图的深度优先遍历 6.1.4 图的宽度优先遍历 6.2 题目描述 你这个学期必须选修 numCourses 门课程记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出其中 prerequisites[i] [ai, bi] 表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如先修课程对 [0, 1] 表示想要学习课程 0 你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习如果可以返回 true 否则返回 false 。 6.3 分析 6.4 C代码实现
struct GraphNode{int label;vectorGraphNode* neighbors;GraphNode(int x):label(x){};
};
class Solution {
public:bool canFinish(int numCourses, vectorvectorint prerequisites) {vectorGraphNode* graph;vectorint degree;for(int i0;inumCourses;i){graph.push_back(new GraphNode(i));degree.push_back(0);}for(int i0;iprerequisites.size();i){GraphNode* begingraph[prerequisites[i][1]];GraphNode* endgraph[prerequisites[i][0]];begin-neighbors.push_back(end);degree[prerequisites[i][0]];}queueGraphNode* Q;for(int i0;inumCourses;i){if(degree[i]0){Q.push(graph[i]);}}while(!Q.empty()){GraphNode* nodeQ.front();Q.pop();for(int i0;inode-neighbors.size();i){degree[node-neighbors[i]-label]--;if(degree[node-neighbors[i]-label]0){Q.push(node-neighbors[i]);}}}for(int i0;inumCourses;i){delete graph[i];}for(int i0;idegree.size();i){if(degree[i]){return false;}}return true;}
};
