【二叉树进阶】--- 根据二叉树创建字符串

这篇文章介绍了【二叉树进阶】--- 根据二叉树创建字符串，分享给大家做个参考，收藏Python资料网收获更多编程知识

 Welcome to 9ilk's Code World

       

(๑•́ ₃ •̀๑) 个人主页:        9ilk

(๑•́ ₃ •̀๑) 文章专栏：     数据结构 

---

从本篇文章开始，博主将分享一些结合二叉树的进阶算法题。

---

🏠 根据二叉树创建字符串

📌 题目内容

根据二叉树创建字符串

📌 题目解析

本题有几个点需要注意：

• 题目需要我们按前序遍历去构建字符串，遇到为空的节点用()表示。
• 在不破坏映射的前提下，空括号是可以省略的。比如：当右子树不为空时，左子树为空的时候空括号不能省略，因为这样就分不清这个节点是连在根的左子树还是右子树了。

📌 算法分析

1. 我们将PreOrder()看作一个具有帮我们分别将根-左子树-右子树的值添加进字符串的功能的函数，按照这个顺序进行递归。

2.什么时候需要加括号：a.当右子树不为空的时候，左子树无论是否有节点都是要加上空括号的，

b.当右子树为空时，右子树的空括号是可以省略的。

3.递归终止条件：遇到空节点并停止递归。

4.在C++中添加字符到字符串中，我们直接调用+=就方便许多了。

参考代码：

  void PreOrder(string& str, TreeNode* root)
    {  //叶子节点的括号才能忽略
        if (root == nullptr)
            return;
        // 
        str += to_string(root->val);
        //访问左子树 右子树和左子树不为空都需要加括号 
        if (root->left || root->right) //非叶子节点的左为空不能忽略
        {   
             str += '(';
            PreOrder(str, root->left);
            str += ')';
        }
        //访问右子树 
        if (root->right)
        {
            str += '(';
            PreOrder(str,root->right);
            str += ')';
        }
    
    }

    string tree2str(TreeNode* root)
    {
        string str;
        PreOrder(str, root);
        return str;
    }

---

🏠 二叉树的层序遍历II

📌 题目内容

二叉树的层序遍历II

📌 题目解析

• 题目要求我们返回的是一个二维数组，二维数组内的每一个一维数组是这个二叉树每一层的结点
• 最后要我们返回的是从最后一层到第一层的二维数组，但是每一层节点的顺序是从左到右。

📌 算法分析

✏️ 思路一：

1. 我们二叉树的层序遍历是借助一个队列，利用“一父带两娃”的思想(即一个父亲入队的时候，它的两个孩子也一起入队)实现。

2.本道题重点是采用层序遍历的思想，我们无法具体划分出每个节点归属的层次。

3.我们可以再开一个队列，用来存每个节点所对应的层次。当一个父亲(层次是h)入队时，那他的两个孩子对应的层次就是h+1；同时当一个节点出队时，他对应高度也对应出。

4.为了效率，我们可以先计算总的高度，提前开好二维数组所需要的层数；但是注意resize之后就不要调用push_back，因为push_back会新开空间。

5.我们按上面流程得到的是从上到下的层序遍历，从下往上我们可以使用reverse算法进行逆置。

参考代码：

   //求高度
    int height(TreeNode* root)
    {
        if (root == nullptr)
            return 0;
        int left = height(root->left);
        int right = height(root->right);
        return left > right ? left + 1 :right + 1;
    }

    vector<vector<int>> levelOrder(TreeNode* root)
    {
        vector<vector<int>> vv;
        if(root == nullptr)
          return vv;
         int Height = height(root);
        //预先开好层数空间 
        vv.resize(Height);
        queue<TreeNode*> treeq;
        queue<int> levelq;
        levelq.push(1);//根节点是第一层
        treeq.push(root);
        vv[0].push_back(root->val);
        while(!treeq.empty())
        {
           TreeNode* front = treeq.front();
           treeq.pop();           
           int levelsize = levelq.front();
           levelq.pop();
           if(front->left)  //一父带两娃的同时也push对应高度
           {
               treeq.push(front->left);
               levelq.push(levelsize+1);
               vv[levelsize].push_back(front->left->val); //push进对应层数的数组
           }  

           if(front->right)
           {
               treeq.push(front->right);
               levelq.push(levelsize+1);
               vv[levelsize].push_back(front->right->val);
           }  

        }
      reverse(vv.begin(),vv.end());
      return vv;
    }

✏️ 思路二：

1.了解思路一后，我们发现思路一维护每个结点的层数比较麻烦，我们能否另寻他路，一口气把每层的结点push进数组里？

2.我们用levelsize表示每一层结点个数，假设有颗满二叉树，当根结点入队时顺便此时他的左右结点也顺便入队，此时队列中结点的个数就是2，此时这两个结点对应层数就是2；类似地当第二层的两结点一父带两娃时，此时入队了4个结点，这一层也是有4个结点。因此，每次“一父带两娃”后队列内的结点个数就是他们对应的层数，利用这个levelsize进行一个循环，把这一层的结点都push进对应层的数组内。

动图演示：

参考代码：

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root)
    {
      queue<TreeNode*> tq;
      vector<vector<int>> vv;
      if(root == nullptr)
         return vv;
       tq.push(root);
       int levelsize = 1; 
       //层数表示了要“一父带两娃”的次数 也就是上一层带入的孩子总个数
      // vv.push_back(vector<int>({root->val}));
      vector<int> del = {root->val};
      vv.push_back(del);
      while(!tq.empty()) //也可以是levelsize ！= 0
      {
        vector<int> v;
         while(levelsize--) 
        {
             TreeNode* front = tq.front();//一父带两娃    
             tq.pop();
             if(front->left)
            {
             tq.push(front->left);
             v.push_back(front->left->val);  
            }
             if(front->right)
            {
             tq.push(front->right);
             v.push_back(front->right->val);  
            }
        }
         levelsize = tq.size();
           if(v.size())
            vv.push_back(v);
      }
       reverse(vv.begin(),vv.end());
       return vv;
    }
};

---

完(๑¯ω¯๑)

版权声明：本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！