笔试面试题——二叉树进阶（一）

📘北尘_：个人主页
🌎个人专栏:《Linux操作系统》《经典算法试题 》《C++》 《数据结构与算法》

☀️走在路上，不忘来时的初心

---

一、根据二叉树创建字符串

1、题目讲解

2、思路讲解

3、代码实现

class Solution {
public:string tree2str(TreeNode* root) {string s;if(root==nullptr)return s;s+=to_string(root->val);if(root->left  || (root->left==nullptr && root->right)){s+='(';s+=tree2str(root->left);s+=')';}if(root->right){s+='(';s+=tree2str(root->right);s+=')';}return s;}
};

---

二、二叉树的分层遍历

1、题目讲解

2、思路讲解

3、代码实现

class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> s;vector<vector<int>>  vv;int levelsize;if(root){s.push(root);levelsize=1;}while(!s.empty()){vector<int> v;while(levelsize--){TreeNode* front=s.front();s.pop();v.push_back(front->val);if(front->left)s.push(front->left);if(front->right)s.push(front->right);    }vv.push_back(v);levelsize=s.size();}return vv;}
};

---

三、二叉树的最近公共祖先

1、题目讲解

2、思路讲解+递归展开图

思路一：

思路二：

3、代码实现

代码一：

class Solution {
public:bool find(TreeNode* root,TreeNode* x){if(root==nullptr)return  false;if(root==x)return true;return (find(root->left,x)||find(root->right,x));}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==p || root==q)return root;bool pleft=find(root->left,p);bool pright=!pleft;bool qleft=find(root->left,q);bool qright=!qleft;if((pleft && qright) || (pright && qleft)){return root;}if(pleft && qleft){return lowestCommonAncestor(root->left,p,q);}if(pright && qright){return lowestCommonAncestor(root->right,p,q);}return nullptr;}
};

代码二：

class Solution {
public:bool findpath(TreeNode* root,TreeNode* x,stack<TreeNode*>& st){if(root==nullptr)return false;st.push(root);if(root==x)return true;if(findpath(root->left,x,st))return true;if(findpath(root->right,x,st))return true;st.pop();return false;   }TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {stack<TreeNode*> ppath,qpath;findpath(root,p,ppath);findpath(root,q,qpath);while(ppath.size()!=qpath.size()){if(ppath.size()>qpath.size())ppath.pop();elseqpath.pop();}while(ppath.top()!=qpath.top()){ppath.pop();qpath.pop();}return  qpath.top();      }
};

---