编程题分类——树
前言
技巧
- 前序/后序+中序序列可以唯一确定一棵二叉树。递归建树。
正文
1. 按之字形顺序打印二叉树
code
/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};
*/
class Solution {
public:vector<vector<int> > Print(TreeNode* root) {vector<vector<int>> arr_out;vector<int> arr_small;if(root==nullptr)return arr_out;stack<TreeNode*> st1;stack<TreeNode*> st2;st1.push(root);while(!st1.empty()||!st2.empty()){while(!st1.empty()){TreeNode* temp1 = st1.top();arr_small.push_back(temp1->val);if(temp1->left)st2.push(temp1->left);if(temp1->right)st2.push(temp1->right);st1.pop();}if(arr_small.size()){arr_out.push_back(arr_small);arr_small.clear();}while(!st2.empty()){TreeNode* temp2 = st2.top();arr_small.push_back(temp2->val);if(temp2->right)st1.push(temp2->right);if(temp2->left)st1.push(temp2->left);st2.pop();} if(arr_small.size()){arr_out.push_back(arr_small);arr_small.clear();}}return arr_out;}};
2. 层序遍历二叉树
反正就是用队列。
code
void layerTrace(BTreeNode *T)
{if(T== nullptr)//先判断这棵树是否为空return;BTreeNode *p=T;queue<BTreeNode*>q;q.push(p);//然后让头结点先入队列while(!q.empty())//这里可以去判断队列是否非空{p=q.front();//队列中的元素出来,q.pop();cout<<<<p->data;if(p->left!= nullptr)q.push(p->left);//找左子树,让其入队列if(p->right!= nullptr)q.push(p->right);//找,让其入队列右子树}
}
3. 完全二叉树怎么判断?
思路:转变思路,如何判断该树不是完全二叉树,就是层序遍历已经输出null节点了,后面却还有节点。
完全二叉树的性质:从根往下数,除了最下层外都是全满(都有两个子节点),而最下层所有叶结点都向左边靠拢填满。
code
class Solution
{
public:bool isCompleteTree(TreeNode* root){queue<TreeNode*> q;bool reachNull = false;q.push(root);while (!q.empty()){TreeNode* cur = q.front();q.pop();if (cur == nullptr){reachNull = true;continue;}else{if (reachNull){return false;}q.push(cur->left);q.push(cur->right);}}return true;}
};
3、 二叉树的序列化和反序列化
答案class Solution {
public:string preOrder(TreeNode *root){if(root==nullptr)return "#";string ret;ret += to_string(root->val)+'!';ret += preOrder(root->left);ret += preOrder(root->right);return ret;}char retStr[1000]={};char* Serialize(TreeNode *root) { //二叉树的序列化 //首先,序列化可以使用前序,或是层序遍历都行,这里使用前序string temp = preOrder(root);for(int i = 0;i<temp.length();i++){retStr[i] = temp[i];}return retStr;}int stringlen = 0;int pos = 0;TreeNode* buildTree(char *str){if(str[pos]=='#'){pos++;return NULL;}int val = 0;while(str[pos]!='!')//在遇到!之前的那个数字,将其存储下来。{val = 10*val+str[pos]-'0';//这里的val,我之前多声明了一次,导致出错,这个错误不应该犯pos++;} pos++;TreeNode *root2 = new TreeNode(val);if(pos<stringlen)root2->left = buildTree(str);if(pos<stringlen)root2->right = buildTree(str);return root2;}TreeNode* Deserialize(char *str) {//二叉树的反序列化stringlen = strlen(str);TreeNode* root = buildTree(str);return root; }
};
4. 二叉搜索树的第k个结点
题目
方法一:
code
/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};
*/
class Solution {
public:TreeNode* res;TreeNode* KthNode(TreeNode* root, int k) {inOrder(root,k);return res;}void inOrder(TreeNode* root,int& k){//中序遍历,第k个节点即为所求的节点if(root==nullptr)return;if(root->left)inOrder(root->left,k);k--;//error1:要先进行减法if(k==0)res = root;if(root->right)inOrder(root->right,k);}
};
方法二:非递归的方式,维护一个栈。
答案/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};
*/
class Solution {
public:TreeNode* KthNode(TreeNode* root, int k) {//中序遍历,非递归的话,需要维护一个栈stack<TreeNode*> st;TreeNode* res = NULL;//error3:要最终返回的元素,一般要记得进行初始化int n = 0;TreeNode* cur = root;while(!st.empty()||cur){while(cur){st.push(cur);cur = cur->left;}cur= st.top();//error1:注意当前栈顶元素要赋给curn++;st.pop();if(n==k){res = cur;return res;}cur = cur->right;//error2:直接把当前元素的右节点也放入栈即可}return res;}
};
5. 重建二叉树
题目
code
/*** Definition for binary tree* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {if(pre.size()==0||vin.size()==0)return nullptr;int rootVal = pre[0];int rootIndex = 0;TreeNode* root = new TreeNode(rootVal);for(int i = 0;i<vin.size();i++){if(vin[i]==rootVal){rootIndex = i;break;}}vector<int> pre_left;vector<int> vin_left;vector<int> pre_right;vector<int> vin_right;for(int j = 0;j<rootIndex;j++){pre_left.push_back(pre[j+1]);vin_left.push_back(vin[j]);}for(int k = rootIndex+1;k<vin.size();k++){pre_right.push_back(pre[k]);vin_right.push_back(vin[k]);}root->left = reConstructBinaryTree(pre_left,vin_left);root->right = reConstructBinaryTree(pre_right,vin_right);return root;}
};
6. 树的子结构
题目
code
/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:bool HasSubtree(TreeNode* root1, TreeNode* root2) {if(root1==nullptr||root2==nullptr)return false;bool result;if(root1->val==root2->val)//如果当前的节点是相等的,就继续递归比较其他节点{result = Hastree(root1,root2);}if(!result){result = HasSubtree(root1->left,root2); //否则就拿左节点和子结构进行比较}if(!result){result = HasSubtree(root1->right,root2);//否则就拿右节点和子结构进行比较}return result;}bool Hastree(TreeNode* root1,TreeNode* root2){if(root2==NULL)return true;if(root1==NULL)return false;if(root1->val!=root2->val)return false;return Hastree(root1->left,root2->left)&&Hastree(root1->right,root2->right);}
};
7. 二叉树的镜像
题目
code
/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param pRoot TreeNode类 * @return TreeNode类*/TreeNode* Mirror(TreeNode* root) {//类似于后序遍历if(root==nullptr)return nullptr;Mirror(root->left);Mirror(root->right);TreeNode* temp = root->left;root->left = root->right;root->right = temp;return root;}
};
8. 二叉树的最近公共祖先
题目
///
/*** 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) {if(root==nullptr||root==p||root==q)return root;TreeNode* left = lowestCommonAncestor(root->left,p,q);TreeNode* right = lowestCommonAncestor(root->right,p,q);if(left!=nullptr&&right!=nullptr)return root;else if(left!=nullptr)return left;else if(right!=nullptr)return right;return nullptr;}
};
9. 二叉树的遍历(前序,中序,后序,递归+迭代 )
9.1 前序遍历
9_1_1. 前序遍历(递归)
答案class Solution {
public:void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;vec.push_back(cur->val); // 中traversal(cur->left, vec); // 左traversal(cur->right, vec); // 右}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};
9_1_2.前序遍历(迭代)
code
vector<int> preorder(TreeNode* root)
{vector<int> res;if(root==NULL)return res;stack<TreeNode*> st;st.push(root);while(!st.empty()){TreeNode* node = st.top();res.push(node);st.pop();if(node->right)st.push(node->right);if(node->left)st.push(node.left);}return result;
}
9.2 中序遍历
9_2_1. 中序遍历递归
递归class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec); // 左vec.push_back(cur->val); // 中traversal(cur->right, vec); // 右}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};
9_2_2.中序遍历迭代
答案/*** 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:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode* cur = root;while(cur!=NULL||!st.empty()){if(cur!=NULL)//将入栈和出栈动作分开{st.push(cur);cur = cur->left;//左}else//这个是出栈的动作{cur = st.top();st.pop();result.push_back(cur->val);//中cur = cur->right;//右}}return result;}
};
9.3 后序遍历
9.3.1 后序遍历递归
答案class Solution {
public:void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec); // 左traversal(cur->right, vec); // 右vec.push_back(cur->val); // 中}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};
9.3.2 后序遍历迭代
答案/*** 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:vector<int> postorderTraversal(TreeNode* root) {vector<int> res;if(root==nullptr)return res;stack<TreeNode*> st;st.push(root);while(!st.empty()){TreeNode* node = st.top();res.push_back(node->val);st.pop();if(node->left)st.push(node->left);if(node->right)st.push(node->right);}reverse(res.begin(),res.end());return res;}
};
10. 二叉树的最近公共祖先
题目
code
/*** 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) {//首先判断某节点是不是另一个节点子节点//看能不能把子结构的那道题目给套进来。if(root==nullptr||root==p||root==q)return root;TreeNode* left = lowestCommonAncestor(root->left,p,q);TreeNode* right = lowestCommonAncestor(root->right,p,q);if(left!=nullptr&&right!=nullptr)return root;else if(left!=nullptr)return left;else if(right!=nullptr)return right;return nullptr;}
};
这道题目应该就是普通的递归,其实跟回溯应该没什么关系了,可能一讲到二叉树,大部分的思路应该都要是递归的思路会比较对。
11. 二叉搜索树中的插入操作
题目
解题思路
此题的解题核心,还是说要找到合适的位置,去插入这个节点。
那么插入有两种方式,
第一:按照普通的插入方式,让parent节点指向当前要插入的这个位置。我当时也是觉得这个位置很难找。
第二:采用递归的方式,找到合适的位置,返回这个插入的节点就可以了。
代码
方法一
答案/*** 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:TreeNode* insertIntoBST(TreeNode* root, int val) {if(root==nullptr){root = new TreeNode(val);return root;}if(val>root->val){root->right = insertIntoBST(root->right,val);}else{root->left = insertIntoBST(root->left,val);}return root;}
};
方法二
code
/*** 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:TreeNode* insertIntoBST(TreeNode* root, int val) {if(root==nullptr){root = new TreeNode(val);return root;}TreeNode* parent = nullptr;bst(root,val,parent);return root;}void bst(TreeNode* cur,int val,TreeNode* parent){if(cur==nullptr){TreeNode* node = new TreeNode(val);if(val>parent->val)parent->right = node;elseparent->left = node;return;}parent = cur;if(parent->val>val)bst(cur->left,val,parent);elsebst(cur->right,val,parent);}
};
12. 二叉树的最大深度
二叉树的最大深度
方法一:递归
code
/*** 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:int maxDepth(TreeNode* root) {if(root==nullptr)return 0;int left = maxDepth(root->left);//计算左节点int right = maxDepth(root->right);//计算右子树return max(left,right)+1;}
};
方法二:迭代
code
/*** 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:int maxDepth(TreeNode* root) {//13:52->//弄一个队列来保存这些数值if(root==nullptr)return 0;queue<TreeNode*> q;q.push(root);int count=0;while(!q.empty()){int size = q.size();for(int i = 0;i<size;i++){TreeNode* node = q.front();//取出元素q.pop();if(node->left)//加入其孩子节点q.push(node->left);if(node->right)q.push(node->right);}count++;}return count;}
};
方法三:前序遍历 回溯——从上往下找
code
/*** 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:int result = 0;int maxDepth(TreeNode* root) {if(root==nullptr)return 0;getDepth(root,1);return result;}void getDepth(TreeNode* node,int depth){if(result<depth)result = depth;if(node->left==nullptr&&node->right==nullptr)return;if(node->left) {depth++;getDepth(node->left,depth);depth--;}if(node->right){depth++;getDepth(node->right,depth);depth--;}return;}
};
13. 左叶子之和
题目
方法1:迭代 code
/*** 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:int sumOfLeftLeaves(TreeNode* root) {//递归不会用迭代的方式if(root==nullptr)return 0;queue<TreeNode*> q;q.push(root);int sum = 0;while(!q.empty()){int size = q.size();for(int i = 0;i<size;i++){TreeNode* node = q.front();if(node->left){if(node->left->left==nullptr&&node->left->right==nullptr)//error1:疏忽了左叶子节点的定义sum+=node->left->val;q.push(node->left);}if(node->right){q.push(node->right);}q.pop();}}return sum;}
};
方法二:递归法
code
/*** 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:int sum = 0;int sumOfLeftLeaves(TreeNode* root) {if(root==nullptr)return 0;int left = sumOfLeftLeaves(root->left);int right = sumOfLeftLeaves(root->right);if(root->left){if(root->left->left==nullptr&&root->left->right==nullptr)sum+=root->left->val;}return sum;}};
14. 从上到下_找树左下角的值
答案/*** 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:int maxLen = INT_MIN;int maxValue;int findBottomLeftValue(TreeNode* root) {//已经假设至少有一个节点了,所以不用判空dfs(root,0);return maxValue;}void dfs(TreeNode* root,int leftLen){if(root->left==nullptr&&root->right==nullptr){if(leftLen>maxLen){maxLen = leftLen;maxValue = root->val;}}if(root->left){leftLen++;dfs(root->left,leftLen);leftLen--;}if(root->right){leftLen++;dfs(root->right,leftLen);leftLen--;}}
};
参考
- 剑指Offer
- Leetcode 100题
编程题分类——树
前言
技巧
- 前序/后序+中序序列可以唯一确定一棵二叉树。递归建树。
正文
1. 按之字形顺序打印二叉树
code
/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};
*/
class Solution {
public:vector<vector<int> > Print(TreeNode* root) {vector<vector<int>> arr_out;vector<int> arr_small;if(root==nullptr)return arr_out;stack<TreeNode*> st1;stack<TreeNode*> st2;st1.push(root);while(!st1.empty()||!st2.empty()){while(!st1.empty()){TreeNode* temp1 = st1.top();arr_small.push_back(temp1->val);if(temp1->left)st2.push(temp1->left);if(temp1->right)st2.push(temp1->right);st1.pop();}if(arr_small.size()){arr_out.push_back(arr_small);arr_small.clear();}while(!st2.empty()){TreeNode* temp2 = st2.top();arr_small.push_back(temp2->val);if(temp2->right)st1.push(temp2->right);if(temp2->left)st1.push(temp2->left);st2.pop();} if(arr_small.size()){arr_out.push_back(arr_small);arr_small.clear();}}return arr_out;}};
2. 层序遍历二叉树
反正就是用队列。
code
void layerTrace(BTreeNode *T)
{if(T== nullptr)//先判断这棵树是否为空return;BTreeNode *p=T;queue<BTreeNode*>q;q.push(p);//然后让头结点先入队列while(!q.empty())//这里可以去判断队列是否非空{p=q.front();//队列中的元素出来,q.pop();cout<<<<p->data;if(p->left!= nullptr)q.push(p->left);//找左子树,让其入队列if(p->right!= nullptr)q.push(p->right);//找,让其入队列右子树}
}
3. 完全二叉树怎么判断?
思路:转变思路,如何判断该树不是完全二叉树,就是层序遍历已经输出null节点了,后面却还有节点。
完全二叉树的性质:从根往下数,除了最下层外都是全满(都有两个子节点),而最下层所有叶结点都向左边靠拢填满。
code
class Solution
{
public:bool isCompleteTree(TreeNode* root){queue<TreeNode*> q;bool reachNull = false;q.push(root);while (!q.empty()){TreeNode* cur = q.front();q.pop();if (cur == nullptr){reachNull = true;continue;}else{if (reachNull){return false;}q.push(cur->left);q.push(cur->right);}}return true;}
};
3、 二叉树的序列化和反序列化
答案class Solution {
public:string preOrder(TreeNode *root){if(root==nullptr)return "#";string ret;ret += to_string(root->val)+'!';ret += preOrder(root->left);ret += preOrder(root->right);return ret;}char retStr[1000]={};char* Serialize(TreeNode *root) { //二叉树的序列化 //首先,序列化可以使用前序,或是层序遍历都行,这里使用前序string temp = preOrder(root);for(int i = 0;i<temp.length();i++){retStr[i] = temp[i];}return retStr;}int stringlen = 0;int pos = 0;TreeNode* buildTree(char *str){if(str[pos]=='#'){pos++;return NULL;}int val = 0;while(str[pos]!='!')//在遇到!之前的那个数字,将其存储下来。{val = 10*val+str[pos]-'0';//这里的val,我之前多声明了一次,导致出错,这个错误不应该犯pos++;} pos++;TreeNode *root2 = new TreeNode(val);if(pos<stringlen)root2->left = buildTree(str);if(pos<stringlen)root2->right = buildTree(str);return root2;}TreeNode* Deserialize(char *str) {//二叉树的反序列化stringlen = strlen(str);TreeNode* root = buildTree(str);return root; }
};
4. 二叉搜索树的第k个结点
题目
方法一:
code
/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};
*/
class Solution {
public:TreeNode* res;TreeNode* KthNode(TreeNode* root, int k) {inOrder(root,k);return res;}void inOrder(TreeNode* root,int& k){//中序遍历,第k个节点即为所求的节点if(root==nullptr)return;if(root->left)inOrder(root->left,k);k--;//error1:要先进行减法if(k==0)res = root;if(root->right)inOrder(root->right,k);}
};
方法二:非递归的方式,维护一个栈。
答案/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};
*/
class Solution {
public:TreeNode* KthNode(TreeNode* root, int k) {//中序遍历,非递归的话,需要维护一个栈stack<TreeNode*> st;TreeNode* res = NULL;//error3:要最终返回的元素,一般要记得进行初始化int n = 0;TreeNode* cur = root;while(!st.empty()||cur){while(cur){st.push(cur);cur = cur->left;}cur= st.top();//error1:注意当前栈顶元素要赋给curn++;st.pop();if(n==k){res = cur;return res;}cur = cur->right;//error2:直接把当前元素的右节点也放入栈即可}return res;}
};
5. 重建二叉树
题目
code
/*** Definition for binary tree* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {if(pre.size()==0||vin.size()==0)return nullptr;int rootVal = pre[0];int rootIndex = 0;TreeNode* root = new TreeNode(rootVal);for(int i = 0;i<vin.size();i++){if(vin[i]==rootVal){rootIndex = i;break;}}vector<int> pre_left;vector<int> vin_left;vector<int> pre_right;vector<int> vin_right;for(int j = 0;j<rootIndex;j++){pre_left.push_back(pre[j+1]);vin_left.push_back(vin[j]);}for(int k = rootIndex+1;k<vin.size();k++){pre_right.push_back(pre[k]);vin_right.push_back(vin[k]);}root->left = reConstructBinaryTree(pre_left,vin_left);root->right = reConstructBinaryTree(pre_right,vin_right);return root;}
};
6. 树的子结构
题目
code
/*
struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}
};*/
class Solution {
public:bool HasSubtree(TreeNode* root1, TreeNode* root2) {if(root1==nullptr||root2==nullptr)return false;bool result;if(root1->val==root2->val)//如果当前的节点是相等的,就继续递归比较其他节点{result = Hastree(root1,root2);}if(!result){result = HasSubtree(root1->left,root2); //否则就拿左节点和子结构进行比较}if(!result){result = HasSubtree(root1->right,root2);//否则就拿右节点和子结构进行比较}return result;}bool Hastree(TreeNode* root1,TreeNode* root2){if(root2==NULL)return true;if(root1==NULL)return false;if(root1->val!=root2->val)return false;return Hastree(root1->left,root2->left)&&Hastree(root1->right,root2->right);}
};
7. 二叉树的镜像
题目
code
/*** struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param pRoot TreeNode类 * @return TreeNode类*/TreeNode* Mirror(TreeNode* root) {//类似于后序遍历if(root==nullptr)return nullptr;Mirror(root->left);Mirror(root->right);TreeNode* temp = root->left;root->left = root->right;root->right = temp;return root;}
};
8. 二叉树的最近公共祖先
题目
///
/*** 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) {if(root==nullptr||root==p||root==q)return root;TreeNode* left = lowestCommonAncestor(root->left,p,q);TreeNode* right = lowestCommonAncestor(root->right,p,q);if(left!=nullptr&&right!=nullptr)return root;else if(left!=nullptr)return left;else if(right!=nullptr)return right;return nullptr;}
};
9. 二叉树的遍历(前序,中序,后序,递归+迭代 )
9.1 前序遍历
9_1_1. 前序遍历(递归)
答案class Solution {
public:void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;vec.push_back(cur->val); // 中traversal(cur->left, vec); // 左traversal(cur->right, vec); // 右}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};
9_1_2.前序遍历(迭代)
code
vector<int> preorder(TreeNode* root)
{vector<int> res;if(root==NULL)return res;stack<TreeNode*> st;st.push(root);while(!st.empty()){TreeNode* node = st.top();res.push(node);st.pop();if(node->right)st.push(node->right);if(node->left)st.push(node.left);}return result;
}
9.2 中序遍历
9_2_1. 中序遍历递归
递归class Solution {
public:
void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec); // 左vec.push_back(cur->val); // 中traversal(cur->right, vec); // 右}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};
9_2_2.中序遍历迭代
答案/*** 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:vector<int> inorderTraversal(TreeNode* root) {vector<int> result;stack<TreeNode*> st;TreeNode* cur = root;while(cur!=NULL||!st.empty()){if(cur!=NULL)//将入栈和出栈动作分开{st.push(cur);cur = cur->left;//左}else//这个是出栈的动作{cur = st.top();st.pop();result.push_back(cur->val);//中cur = cur->right;//右}}return result;}
};
9.3 后序遍历
9.3.1 后序遍历递归
答案class Solution {
public:void traversal(TreeNode* cur, vector<int>& vec) {if (cur == NULL) return;traversal(cur->left, vec); // 左traversal(cur->right, vec); // 右vec.push_back(cur->val); // 中}vector<int> preorderTraversal(TreeNode* root) {vector<int> result;traversal(root, result);return result;}
};
9.3.2 后序遍历迭代
答案/*** 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:vector<int> postorderTraversal(TreeNode* root) {vector<int> res;if(root==nullptr)return res;stack<TreeNode*> st;st.push(root);while(!st.empty()){TreeNode* node = st.top();res.push_back(node->val);st.pop();if(node->left)st.push(node->left);if(node->right)st.push(node->right);}reverse(res.begin(),res.end());return res;}
};
10. 二叉树的最近公共祖先
题目
code
/*** 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) {//首先判断某节点是不是另一个节点子节点//看能不能把子结构的那道题目给套进来。if(root==nullptr||root==p||root==q)return root;TreeNode* left = lowestCommonAncestor(root->left,p,q);TreeNode* right = lowestCommonAncestor(root->right,p,q);if(left!=nullptr&&right!=nullptr)return root;else if(left!=nullptr)return left;else if(right!=nullptr)return right;return nullptr;}
};
这道题目应该就是普通的递归,其实跟回溯应该没什么关系了,可能一讲到二叉树,大部分的思路应该都要是递归的思路会比较对。
11. 二叉搜索树中的插入操作
题目
解题思路
此题的解题核心,还是说要找到合适的位置,去插入这个节点。
那么插入有两种方式,
第一:按照普通的插入方式,让parent节点指向当前要插入的这个位置。我当时也是觉得这个位置很难找。
第二:采用递归的方式,找到合适的位置,返回这个插入的节点就可以了。
代码
方法一
答案/*** 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:TreeNode* insertIntoBST(TreeNode* root, int val) {if(root==nullptr){root = new TreeNode(val);return root;}if(val>root->val){root->right = insertIntoBST(root->right,val);}else{root->left = insertIntoBST(root->left,val);}return root;}
};
方法二
code
/*** 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:TreeNode* insertIntoBST(TreeNode* root, int val) {if(root==nullptr){root = new TreeNode(val);return root;}TreeNode* parent = nullptr;bst(root,val,parent);return root;}void bst(TreeNode* cur,int val,TreeNode* parent){if(cur==nullptr){TreeNode* node = new TreeNode(val);if(val>parent->val)parent->right = node;elseparent->left = node;return;}parent = cur;if(parent->val>val)bst(cur->left,val,parent);elsebst(cur->right,val,parent);}
};
12. 二叉树的最大深度
二叉树的最大深度
方法一:递归
code
/*** 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:int maxDepth(TreeNode* root) {if(root==nullptr)return 0;int left = maxDepth(root->left);//计算左节点int right = maxDepth(root->right);//计算右子树return max(left,right)+1;}
};
方法二:迭代
code
/*** 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:int maxDepth(TreeNode* root) {//13:52->//弄一个队列来保存这些数值if(root==nullptr)return 0;queue<TreeNode*> q;q.push(root);int count=0;while(!q.empty()){int size = q.size();for(int i = 0;i<size;i++){TreeNode* node = q.front();//取出元素q.pop();if(node->left)//加入其孩子节点q.push(node->left);if(node->right)q.push(node->right);}count++;}return count;}
};
方法三:前序遍历 回溯——从上往下找
code
/*** 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:int result = 0;int maxDepth(TreeNode* root) {if(root==nullptr)return 0;getDepth(root,1);return result;}void getDepth(TreeNode* node,int depth){if(result<depth)result = depth;if(node->left==nullptr&&node->right==nullptr)return;if(node->left) {depth++;getDepth(node->left,depth);depth--;}if(node->right){depth++;getDepth(node->right,depth);depth--;}return;}
};
13. 左叶子之和
题目
方法1:迭代 code
/*** 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:int sumOfLeftLeaves(TreeNode* root) {//递归不会用迭代的方式if(root==nullptr)return 0;queue<TreeNode*> q;q.push(root);int sum = 0;while(!q.empty()){int size = q.size();for(int i = 0;i<size;i++){TreeNode* node = q.front();if(node->left){if(node->left->left==nullptr&&node->left->right==nullptr)//error1:疏忽了左叶子节点的定义sum+=node->left->val;q.push(node->left);}if(node->right){q.push(node->right);}q.pop();}}return sum;}
};
方法二:递归法
code
/*** 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:int sum = 0;int sumOfLeftLeaves(TreeNode* root) {if(root==nullptr)return 0;int left = sumOfLeftLeaves(root->left);int right = sumOfLeftLeaves(root->right);if(root->left){if(root->left->left==nullptr&&root->left->right==nullptr)sum+=root->left->val;}return sum;}};
14. 从上到下_找树左下角的值
答案/*** 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:int maxLen = INT_MIN;int maxValue;int findBottomLeftValue(TreeNode* root) {//已经假设至少有一个节点了,所以不用判空dfs(root,0);return maxValue;}void dfs(TreeNode* root,int leftLen){if(root->left==nullptr&&root->right==nullptr){if(leftLen>maxLen){maxLen = leftLen;maxValue = root->val;}}if(root->left){leftLen++;dfs(root->left,leftLen);leftLen--;}if(root->right){leftLen++;dfs(root->right,leftLen);leftLen--;}}
};
参考
- 剑指Offer
- Leetcode 100题