最新消息: USBMI致力于为网友们分享Windows、安卓、IOS等主流手机系统相关的资讯以及评测、同时提供相关教程、应用、软件下载等服务。

编程题分类——树

互联网 admin 2浏览 0评论

编程题分类——树

前言

技巧

  1. 前序/后序+中序序列可以唯一确定一棵二叉树。递归建树。

正文

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--;}}
};

参考

  1. 剑指Offer
  2. Leetcode 100题

编程题分类——树

前言

技巧

  1. 前序/后序+中序序列可以唯一确定一棵二叉树。递归建树。

正文

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--;}}
};

参考

  1. 剑指Offer
  2. Leetcode 100题

与本文相关的文章

发布评论

评论列表 (0)

  1. 暂无评论