企业官网建设流程全解析

递归三部曲：

1.确定递归函数的参数和返回值

2.确定终止条件

3.确定单层递归的逻辑

例：中序遍历：

void oreTraversal(TreeNode* cur,vector<int>& v){

if(cur==nullptr){return;}

oreTraversal(cur->left,v);

v.push_back(cur->val);

oreTraversal(cur->right,v);}

层序遍历二叉树：核心思想为用栈来作为中介，用size作为每次输出的元素个数来控制输出

#include <bits/stdc++.h> using namespace std; struct TreeNode{ int val; TreeNode* left; TreeNode* right; TreeNode():val(0),left(nullptr),right(nullptr){ } TreeNode(int x):val(x),left(nullptr),right(nullptr){ } }; vector<int> fun(TreeNode* root){ queue<TreeNode*> que; vector<int> res; TreeNode* node; if(root!=nullptr){ que.push(root); } while(!que.empty()){ int size=que.size(); while(size--){ node=que.front(); res.push_back(node->val); que.pop(); if(node->left!=nullptr){ que.push(node->left); } if(node->right!=nullptr){ que.push(node->right); } } } return res; } int main(){ TreeNode* node=new TreeNode(6); node->left=new TreeNode(4); node->right=new TreeNode(7); node->left->left=new TreeNode(1); node->left->right=new TreeNode(3); node->right->left=new TreeNode(5); node->right->right=new TreeNode(8); vector<int> res=fun(node); for(int x:res){ cout<<x<<" "; } }

从中序与后序遍历序列构造二叉树

class Solution { public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { if(postorder.size()==0){ return nullptr; } TreeNode* root=new TreeNode(postorder[postorder.size()-1]);//1.找根节点:根节点为后序遍历最后的元素 int index; if(postorder.size()==1){ return root; } for(index=0;index<inorder.size();index++){ if(inorder[index]==root->val){ break;//2.找出根节点在中序数组中的位置:在中序数组中找到根节点对应的下标，那么之后可以分出来根节点左边和右边的元素 } } vector<int> newinorderleft(inorder.begin(),inorder.begin()+index);//左中序数组 index也表示“左”元素个数 //括号里面的 inorder.begin() 和 inorder.begin() + index 代表的是两个迭代器（Iterators），它们定义了一个左闭右开的区间 [begin, end) //end()指向最后一个元素的下一个位置 vector<int> newinorderright(inorder.begin()+index+1,inorder.end());//右中序数组 postorder.resize(postorder.size()-1);//便于有后序数组范围定义 vector<int> newpostorderleft(postorder.begin(),postorder.begin()+newinorderleft.size());//左后序数组 vector<int> newpostorderright(postorder.begin()+newinorderleft.size(),postorder.end());//右后序数组 root->left=buildTree(newinorderleft,newpostorderleft); root->right=buildTree(newinorderright,newpostorderright); return root; } };

从前序与中序遍历序列构造二叉树

class Solution { public: TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if(inorder.size()==0){ return nullptr; } TreeNode* root=new TreeNode(preorder[0]); int index; for(index=0;index<inorder.size();index++){ if(inorder[index]==root->val){ break; } } vector<int> newInorderLeft(inorder.begin(),inorder.begin()+index); vector<int> newInorderRight(inorder.begin()+index+1,inorder.end()); vector<int> newPreorderLeft(preorder.begin()+1,preorder.begin()+1+newInorderLeft.size()); vector<int> newPreorderRight(preorder.begin()+1+newInorderLeft.size(),preorder.end()); root->left=buildTree(newPreorderLeft,newInorderLeft); root->right=buildTree(newPreorderRight,newInorderRight); return root; } };