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

📘北尘_：个人主页
🌎个人专栏:《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();
            else
                qpath.pop();
        }
        while(ppath.top()!=qpath.top())
        {
            ppath.pop();
            qpath.pop();
        }
        return  qpath.top();      
    }
};

---