二叉树常见 oj 题（持续更新中）

2022-10-27
湖南
本文字数：8456 字
阅读完需：约 28 分钟

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

题目介绍：（题目链接）
代码：

class Solution {public:    string tree2str(TreeNode* root) {         string ss;         treecopy(root,ss);         return ss;    }    void treecopy(TreeNode* root,string& str) //传引用减少构造    {        if(root == nullptr)        return ;
        str+= to_string(root->val);
        if(root->left || root -> right)        {            str+="(";           treecopy(root->left,str);            str+=")";        }
        if(root->right)    {        str+="(";           treecopy(root->right,str);            str+=")";    }    }};

复制代码

思路：

利用的是前序遍历

注意：

左子树和右子树的判断条件： 1. if(root->left || root -> right) （假如左子树或者右子树不为空，则执行左） 2. if(root->right) （只有当右子树不为空时，执行右分支）
to_string 的利用
void treecopy(TreeNode* root,string& str) （传引用减少构造）

二：二叉树层序遍历

题目描述：（题目链接）

方法一：

class Solution {public:    vector<vector<int>> levelOrder(TreeNode* root) {        vector<vector<int>> vv;         if(root ==nullptr)         return  vv;
         queue<TreeNode*> q;         q.push(root);         int numsize =1;         while(!q.empty())         {             //一层一层的遍历             vector<int> v;           for(int i=0;i<numsize;i++)           {               TreeNode* cur = q.front();               q.pop();               v.push_back(cur->val);
               if(cur->left)               q.push(cur->left);               if(cur->right)               q.push(cur->right);           }           vv.push_back(v);           numsize = q.size();           }           return vv;

复制代码

思路：

记录当前层数的个数，一层一层的遍历
利用了队列先进先出的特性

注意事项：

注意队列函数的使用： q.front() 取出队头的数据
q,back() 取队尾的数据（需要注意是的栈只能取队尾的数据，不能取对头的）
注意 for 循环的使用和 numsize 的更新，for(int i=0;i<numsize;i++)， numsize = q.size();

方法二：

class Solution {public:    vector<vector<int>> levelOrder(TreeNode* root) {        vector<vector<int>> vv;         if(root ==nullptr)         return  vv;
         queue<TreeNode*> q;         q.push(root);         int numsize =1;         while(!q.empty())         {                        TreeNode* cur = q.front(); //取出队列的头             v.push_back(cur->val);             q.pop();             numsize--;
             if(cur->left)             q.push(cur->left);             if(cur->right)             q.push(cur->right);
             if(numsize==0)             {                 vector<int> tem =v;                 v.clear();                 vv.push_back(tem);                 numsize = q.size();             }         }         return vv;    }};

复制代码

三：二叉树的层序遍历 II

题目描述：（题目链接）
代码：

class Solution {public:    vector<vector<int>> levelOrderBottom(TreeNode* root) {         vector<vector<int>> vv;         if(root ==nullptr)         return  vv;
         queue<TreeNode*> q;         q.push(root);         int numsize =1;         while(!q.empty())         {             //一层一层的遍历             vector<int> v;           for(int i=0;i<numsize;i++)           {               TreeNode* cur = q.front();               q.pop();               v.push_back(cur->val);
               if(cur->left)               q.push(cur->left);               if(cur->right)               q.push(cur->right);           }           numsize =q.size();           vv.push_back(v);         }         reverse(vv.begin(),vv.end());         return vv;    }};

复制代码

思路：

reverse 一下就得到了

四：二叉树的最近公共祖先

题目描述：题目链接
方法一：

class Solution {public:bool find(TreeNode* root, TreeNode* p){    if(root==nullptr)    return false;
    if(root==p)    return true;
     return find(root->right,p) ||  find(root->left,p);}TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {        //特殊情况        if(root== p || root == q)        return root;
        bool IsRightp=find(root->right,p);        bool IsRightq=find(root->right,q);
        bool IsLeftp=!IsRightp;         bool IsLeftq=!IsRightq;
         if(IsLeftp && IsLeftq)//全在左边         {            return  lowestCommonAncestor(root->left,p,q);         }         else if(IsRightp && IsRightq)//全在右边，就玩右边找         {             return lowestCommonAncestor(root->right,p,q);         }         else{             return root;         }    }};

复制代码

思路：

逻辑：找到第一个祖先，有一个节点在祖先的左，有一个节点在祖先的右
.时间复杂度：N*N 算最坏的情况（第一次 findN,第二次 find N-1......），因为 find 的时间复杂度是 O（N）

注意：

bool IsLeftp=!IsRightp;bool IsLeftq=!IsRightq;取反可以就不用再去递归左树了

方法二：

bool findpath(TreeNode* root,stack<TreeNode*>& st,TreeNode* p){      if(root==nullptr)      return false;
      st.push(root); //先将root 入进栈      if(root==p) //找到了    {         return true;    }
    //往左边找    if(findpath(root->left,st,p))     {        return true; //左边找到了    }
      //往右边找    if(findpath(root->right,st,p))     {        return true; //右边找到了    }
     //左右子树都没找到     st.pop();     return false;}    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {        stack<TreeNode*> stp,stq;       findpath(root,stp,p);       findpath(root,stq,q);       int psize = stp.size();       int qsize = stq.size();
       int max = psize >qsize? psize : qsize;       int min = psize+qsize-max;
       stack<TreeNode*>* maxst =  max== psize? &stp : &stq;       stack<TreeNode*>* minst =  max== psize? &stq : &stp; //找到长度大的和长度小的              int  size = max - min;       while(size--)       {           maxst->pop();       }       while(maxst->top()!=minst->top())       {           maxst->pop();           minst->pop();       }       return maxst->top();       }       };

复制代码

思路：
找到 p，q 的路径
他们两个路径的交点就是共同祖先
两个栈交点的问题可以理解为链表交点问题来解决
时间复杂度为 O（N）
注意：

主要是 findpath 函数的实现，主要流程为：
先将 root 入进栈，再判断 root 是否为 P,为 p 则找到了，return true
再判断左子树和右子树， if(findpath(root->left,st,p)) 假如左树找到了，则 return true
假如左右子树都没找到，则 pop 出栈顶的元素

五：二叉树的前中后序遍历（非递归版）

前序

方法一：

通用法，前后中序都基于此思路

class Solution {public:    vector<int> preorderTraversal(TreeNode* root) {       //先将左树全部入栈，再出，入右       stack<TreeNode*> st;       vector<int> v;         //流程法     TreeNode* cur =root; //要访问的树     while(cur || !st.empty())     {         while(cur) //一直往左入         {             v.push_back(cur->val);             st.push(cur);             cur = cur->left;         }         //左边入完了         TreeNode* tem= st.top();         st.pop();         cur = tem->right; //左数完了，再去入右树         }       return v;    }};

复制代码

思路：

先将左子树入栈，边入边 push_back
左边入完了，再将本节点 pop，入右树

注意：

注意判断条件： while(cur || !st.empty()) ，当本节点不为空或者栈不为空的时候，进循环
TreeNode* tem= st.top(); //先将栈顶节点 pop 掉，因为已经 push_back 了 st.pop();cur = tem->right; //左数完了，再去入右树

方法二：

简洁法

class Solution {public:    vector<int> preorderTraversal(TreeNode* root) {       //先将左树全部入栈，再出，入右       stack<TreeNode*> st;       vector<int> v;       //简洁法       if(root==nullptr)       return v;       st.push(root);       while(!st.empty())       {           TreeNode* cur = st.top();           st.pop();           v.push_back(cur->val);
            if(cur->right)                st.push(cur->right);            if(cur->left)            st.push(cur->left);       }           return v;    }};

复制代码

中序

class Solution {public:    vector<int> inorderTraversal(TreeNode* root) {         stack<TreeNode*> st;       vector<int> v;     TreeNode* cur =root; //要访问的树     while(cur || !st.empty())     {         while(cur) //一直往左入         {                          st.push(cur);             cur = cur->left;         }         //左边入完了         TreeNode* tem= st.top();         st.pop();         v.push_back(tem->val); //左子树完了。访问根         cur = tem->right;     }     return v;    }};

复制代码

与前序不同的是 v.push_back(tem->val);的时机

后序

方法一：

将前序的结果反转即可得到后序的结果

方法二：

class Solution {public:    vector<int> postorderTraversal(TreeNode* root) {              vector<int> v;        if(root == nullptr)        return v;
        stack<TreeNode* > st;        TreeNode* cur = root;        TreeNode* prev = nullptr;        while(cur || !st.empty())        {            //先去左边循环            while(cur)            {                st.push(cur);                cur = cur->left;            }
             TreeNode* top = st.top(); //取栈顶的数据
             if(top->right == nullptr || top->right == prev)             {                 v.push_back(top->val);                 st.pop();                 prev =top;             }             else             {                cur = top->right;             }        }        return v;    }};

复制代码

思路：

先入左数
再取栈顶元素
判断，假如（栈顶的右子树为空，或者右子树为之前访问过的节点），就 push_back，再 pop，更新 prev= 栈顶的元素
如果假如不成立，则再取栈顶的左树去找

注意：

注意 if(top->right == nullptr || top->right == prev) 判断条件

六：二叉搜索树与双向链表

题目描述：题目链接
代码：

class Solution {public:    void Inoder(TreeNode* cur,TreeNode*& prev)    {          if(cur==nullptr)             return;                Inoder(cur->left,prev);                cur->left = prev;        if(prev)            prev->right = cur;                prev =cur;         Inoder(cur->right,prev);     }    TreeNode* Convert(TreeNode* pRootOfTree) {        if(pRootOfTree == nullptr)            return pRootOfTree;         TreeNode* prev = nullptr;                Inoder(pRootOfTree,prev);                TreeNode* head = pRootOfTree;        while(head->left)            head = head->left;                return head;    }};

复制代码

思路：

利用中序遍历链接整颗树
用一个 prev 指针指向前一个被访问的节点，然后当前节点的左子树指向 prev，假如 prev 不为空，prev 的右子树指向当前节点，再更新 pre。
最后递归右子树

注意：

注意 prev 要传引用，因为 prev 是要实时变化的
链表的头不要格外的去记录，因为是双向链表，一直往左就找到了

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

题目描述：题目链接
代码：

class Solution {public:     TreeNode* _buildTree(vector<int>& preorder,int& start,     vector<int>& inorder,int left,int right)     {         if(left>right)         return nullptr;
         //先由根构建节点         TreeNode*  root = new TreeNode(preorder[start]);         start++;                    //再利用中序去寻找左右子树的边界          int preleft = left;          int  i = root->val;          while(left<=right)          {              if(i == inorder[left])              {                  break;              }              else              left++;          }         root->left = _buildTree(preorder,start,inorder,preleft,left-1);         root->right = _buildTree(preorder,start,inorder,left+1,right);
         return root;     }    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {              int start =0;           return _buildTree(preorder,start,inorder,0,inorder.size()-1);    }};

复制代码

思路：

利用前序找到根节点，再通过中序找到左右子树，从而构造出了一整颗树

注意：

递归结束的条件：left>right
注意 start 要传引用，因为要实时变化的。

八：后继者

题目：题目链接
代码：

class Solution {public:    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {        if(root==nullptr)        return root;                TreeNode*  cur = inorderSuccessor(root->left,p);        if(cur != nullptr)        return cur;
        if(root->val > p->val) //找到第一个大于P的值        return root;
        return inorderSuccessor(root->right,p);    }};

复制代码

思路：

中序找到第一个比 p 大的值就是后续

九：左子树之和

题目：（题目链接）

方法一：

代码：

class Solution {public:      void _sumOfLeftLeaves(TreeNode* root,int& sum){          if(root == nullptr)              return ;
              if(root->left!=nullptr && root->left->right==nullptr && root->left->left ==nullptr)            sum += root->left->val;                        _sumOfLeftLeaves(root->left,sum);            _sumOfLeftLeaves(root->right,sum);      }    int sumOfLeftLeaves(TreeNode* root) {          int sum=0;            _sumOfLeftLeaves(root,sum);            return sum;    } };

复制代码

方法二：

代码：

class Solution {public:    int sumOfLeftLeaves(TreeNode* root) {          int sum=0;            _sumOfLeftLeaves(root,sum);            return sum;
        if(root==nullptr)        return 0;
        int leftsum = sumOfLeftLeaves(root->left);        int rightsum = sumOfLeftLeaves(root->right);                int tem =0;        if(root->left!=nullptr && root->left->right==nullptr && root->left->left ==nullptr)            tem = root->left->val;
            return leftsum+rightsum+tem;    } };

复制代码

思路：

递归去找左树上和右树上的左叶子节点，相加即可

注意：

特别要注意的是左叶子节点的判断条件：root->left!=nullptr && root->left->right==nullptr && root->left->left ==nullptr

十：找树左下角的值

题目：（题目链接）

方法一：

层序遍历，找到最下面一层，最先从队列里出来的树

方法二：

代码：

class Solution {public:             int high=0,ret=0;//high 来记录当前最左节点的高度，ret记录答案             void _findBottomLeftValue(TreeNode* root,int deep)             {                    if(root==nullptr)                    return;
                    if(root->left==nullptr && root->right ==nullptr) //因为是前序遍历，所以同一高度，左树优先                    {                        if(deep > high)                           {                               ret=root->val;                               high =deep;                           }                    }                    if(root->left)  _findBottomLeftValue(root->left,deep+1);                    if(root->right)  _findBottomLeftValue(root->right,deep+1);             }    int findBottomLeftValue(TreeNode* root) {        ret =root->val;         _findBottomLeftValue(root,high);         return ret;    }};

复制代码

思路：

记录当前最左节点的高度，如果找到叶子节点的高度大于之前的，则该叶子节点为当前树的左下角
因为是前序遍历，所以同一层的，左子树优先，所以可以求出左下角

注意：

注意全局变量的使用

十一：路径总和

题目：（题目链接）
代码：

/** * 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:    bool hasPathSum(TreeNode* root, int targetSum) {        return _hasPathSum(root,0,targetSum);    }   bool  _hasPathSum(TreeNode* root, int curSum,int targetSum)   {       if(root==nullptr)       {         return false;       }       curSum+= root->val;       if(root->left==nullptr && root->right==nullptr)       {           if(curSum == targetSum)           return true;           else           return false;       }       if(_hasPathSum(root->left,curSum,targetSum))       return true;
       if(_hasPathSum(root->right,curSum,targetSum))       return true;
       return false;   }};

复制代码

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

题目：（题目链接）

*代码：

/** * 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* _buildTree(vector<int>& preorder,int& start,     vector<int>& inorder,int left,int right)     {         if(left>right)         return nullptr;
         //先由根构建节点         TreeNode*  root = new TreeNode(preorder[start]);         start++;                    //再利用中序去寻找左右子树的边界          int preleft = left;          int  i = root->val;          while(left<=right)          {              if(i == inorder[left])              {                  break;              }              else              left++;          }         root->left = _buildTree(preorder,start,inorder,preleft,left-1);         root->right = _buildTree(preorder,start,inorder,left+1,right);
         return root;     }    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {              int start =0;           return _buildTree(preorder,start,inorder,0,inorder.size()-1);    }};

复制代码

总结：

二叉树的 oj 题考察的主要是递归思想的运用和非递归时，对整个递归流程的理解。只有理解好递归的整个过程和思路，才能更好地学好二叉树

多写，多思考，多复习，多总结！！

持续更新中！！！

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/4f22231aa5394937d10f212d7】。未经作者许可，禁止转载。

雪芙花

关注

还未添加个人签名 2022-04-28 加入

还未添加个人简介

发布

暂无评论

创作场景

二叉树常见 oj 题（持续更新中）

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

二：二叉树层序遍历

三：二叉树的层序遍历 II

四：二叉树的最近公共祖先

五：二叉树的前中后序遍历（非递归版）

前序

中序

后序

六：二叉搜索树与双向链表

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

八：后继者

九：左子树之和

方法一：

方法二：

十：找树左下角的值

方法一：

方法二：

十一：路径总和

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

总结：

雪芙花

评论

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