当前位置：网站首页>二叉树刷题(二)

二叉树刷题(二)

2022-07-17 12:43:00 【std i hurt o love】

一、按之字形顺序打印二叉树

解法一:非递归(推荐)

  • 先判断二叉树是否为空
  • 建立辅助队列，根节点先入队列，因为无论如何访问，根节点必然是第一个，排在队列前面，设置打印顺序标记量flag，每隔一层转化为false或true，据此判断打印顺序
  • 每入一层，统计队列元素个数，更改flag变量值，当前队列中元素的个数即为该层节点数
  • 遍历一层后，将其弹出队列，存入一维数组中，若有子节点，加入队列进行下一层操作
  • 根据flag变量判定是直接将一维数组加入二维数组，还是反转后再加入
    该题在层序遍历基础上增加了一个flag判断
class Solution {
    
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
    
        TreeNode*cur=pRoot,*p;
        vector<vector<int>>v;
        if(cur==NULL)
            return v;
        queue<TreeNode*>q;
        q.push(cur);//第一行入
        bool flag=true;
        while(!q.empty())
        {
    
            vector<int>tmp;
            int n=q.size();
            flag=!flag;//奇数行反转，偶数行不反转
            for(int i=0;i<n;i++)
            {
    
                p=q.front();
                q.pop();
                tmp.push_back(p->val);
                if(p->left)
                    q.push(p->left);
                if(p->right)
                    q.push(p->right);
            }
            if(flag)//奇数行反转，偶数行不反转
                reverse(tmp.begin(),tmp.end());
            v.push_back(tmp);
        }
        return v;
    }
    
};

时间复杂度:O(n)，reverse时间复杂度为O(n),循环遍历n个节点
空间复杂度:O(n),队列空间n

解法二:递归

在层序递归遍历的基础上设置反转函数
第一个从左到右，第二个，从右到左，每隔一个是相同的
由于单次递归无法存入所有节点，逆序必须在递归完毕，节点存入完毕后进行

class Solution {
    
public:
    void change(vector<vector<int>>&v)
    {
    
        for(int i=0;i<v.size();i++)
        {
    
            if(i%2)//奇数逆序
               reverse(v[i].begin(),v[i].end());
        }
    }
    void _levelorder(vector<vector<int>>&v,TreeNode*root,int depth)
    {
    
       if(root)
       {
    
          if(v.size()<depth)
              v.push_back(vector<int>{
    });
          v[depth-1].push_back(root->val);
       }
        else
            return ;
        _levelorder(v, root->left, depth+1);
        _levelorder(v, root->right, depth+1);
        
    }
    vector<vector<int> > Print(TreeNode* pRoot) {
    
        vector<vector<int>>v;
        if(pRoot==NULL)
            return v;
        _levelorder(v, pRoot, 1);
        change(v);
        return v;
    }
};

时间复杂度:O(n)，reverse空间复杂度O(n)，递归遍历一遍节点
空间复杂度:O(n),递归栈最大深度为n

解法三:双栈法

  • 建立两个辅助栈，每次依次访问s1,s2这两个栈
  • 根据次序，s1必定记录奇数层，那么其子节点依据从左到右的顺序入s2栈，出栈时即为逆序，s2为偶数层，其子节点将以先右后左的顺序入s1栈，出栈即为正序，由此循环
  • 每访问完一层，即有一个栈为空时，将一维数组加入二维数组
class Solution {
    
public:
    vector<vector<int> > Print(TreeNode* pRoot) {
    
        TreeNode*cur=pRoot;
        vector<vector<int>>v;
        if(cur==NULL)
            return v;
        stack<TreeNode*>s1,s2;
        s1.push(cur);//第一层
        while(!s1.empty()||!s2.empty())
        {
    
             vector<int>tmp;
             while(!s1.empty())//遍历奇数层
             {
    
                 TreeNode*node=s1.top();
                 s1.pop();
                 tmp.push_back(node->val);
                 if(node->left)
                     s2.push(node->left);//子节点加入偶数层，入栈正序，出栈时逆序
                 if(node->right)
                     s2.push(node->right);
             }
            if(tmp.size())
                v.push_back(tmp);
            tmp.clear();
             while(!s2.empty())
             {
    
                 TreeNode*node=s2.top();
                 s2.pop();
                 tmp.push_back(node->val);
                 if(node->right)//注意加入顺序的改变，入栈逆序，出栈时正序
                     s1.push(node->right);
                 if(node->left)
                     s1.push(node->left);
             }
             if(tmp.size())
                v.push_back(tmp);
        }
        return v;
    }
};

时间复杂度:O(n),遍历二叉树全部节点
空间复杂度:O(n)，两个栈的空间最坏情况为n

二、二叉树最大深度

深度指树的根节点到任意一叶子节点路径上节点的数量，根节点每次往下一层深度就会加深1，由此二叉树深度就等于根节点的一层加上左子树和右子树深度的最大值

解法一:递归(推荐)

  • 不断向下即子节点递归直到为空
  • 递归反回两边子树的最大值加上本级深度，即加1
  • 每级任务为进入左右子树求其深度
class Solution {
    
public:
    /** * * @param root TreeNode类 * @return int整型 */
    
    int maxDepth(TreeNode* root) {
    
        // write code here
        if(root==NULL)
            return 0;
        return max(maxDepth(root->left),maxDepth(root->right))+1;//取最大节点值加1
    }
};

时间复杂度:O(n),遍历整个二叉树
空间复杂度:O(n),最坏情况二叉树退化为链表，递归栈深度为n

解法二:层次遍历

依据层序遍历，这里去掉存值操作，保留深度即可

  • 用队列记录每层节点
  • 每层遍历时，先统计该层个数，再遍历相应节点
  • 遍历玩一层后，深度加一
class Solution {
    
public:
    /** * * @param root TreeNode类 * @return int整型 */
    int maxDepth(TreeNode* root) {
    
        // write code here
        if(root==NULL)
            return 0;
        queue<TreeNode*>q;
        q.push(root);
        int depth=0;
        while(!q.empty())
        {
    
            int n=q.size();//先记录当前层的节点数
            for(int i=0;i<n;i++)//遍历完该层再进入下一层
            {
    
                TreeNode*node=q.front();
                q.pop();
                if(node->left)
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
            }
            depth++;
        }
        return depth;
    }
};

时间复杂度:O(n),遍历整个二叉树
空间复杂度:O(n),辅助队列空间最大为n

三、 二叉树中和为某一值的路径(一)

题目要求节点只能从上到下

解法一:递归(推荐)

  • 采用递归先序遍历
  • 每次检查节点是否为空
  • 检查遍历节点是否为叶子节点，且当当前sum值等于节点值时找到
  • 检查左右节点是否有可完成路径的，只要有一条即为true，因此采用||判断
class Solution {
    
public:
    /** * * @param root TreeNode类 * @param sum int整型 * @return bool布尔型 */
    bool hasPathSum(TreeNode* root, int sum) {
    
        // write code here
        if(root==NULL)
            return false;
        if(root->left==NULL&&root->right==NULL&&root->val==sum)//当无子节点且sum值减到等于该节点值时，路径存在
            return true;
        return hasPathSum(root->left, sum-root->val)||hasPathSum(root->right, sum-root->val);//左右至少存在一条路径
    }
};

时间复杂度:O(n),遍历整个二叉树
空间复杂度:O(n),最坏情况二叉树退化为链表，递归栈深度为n

解法二:非递归

使用栈辅助，进行dfs遍历

  • 检查空节点
  • 使用两个栈同步遍历，一个记录节点，辅助深度优先搜索，另一个栈记录目前为止的路径和，对c++,则使用一个栈即可，利用pair对组记录两组数据，根节点先入栈
  • 无叶子节点就将左右子节点入栈，并加入路径和
class Solution {
    
public:
    /** * * @param root TreeNode类 * @param sum int整型 * @return bool布尔型 */
    bool hasPathSum(TreeNode* root, int sum) {
    
        // write code here
        if(root==NULL)
            return false;
        stack<pair<TreeNode*,int>>s;//对组，存储节点和累加值
        s.push({
    root,root->val});
        while(!s.empty())
        {
    
            auto tmp=s.top();
            s.pop();
            if(tmp.first->left==NULL&&tmp.first->right==NULL&&tmp.second==sum)//左右都为空，且节点累加值等于sum,找到路径
                return true;
            if(tmp.first->left)//在对其左右子节点判断，入栈
                s.push({
    tmp.first->left,tmp.second+tmp.first->left->val});
            if(tmp.first->right)
                s.push({
    tmp.first->right,tmp.second+tmp.first->right->val});
        }
        return false;//遍历完未找到，不存在，为假
    }
};

时间复杂度:O(n),dfs遍历二叉树所有链表
空间复杂度:O(n),辅助栈最坏为n

原网站

版权声明
本文为[std i hurt o love]所创，转载请带上原文链接，感谢
https://blog.csdn.net/qwer1234mnbv_/article/details/125802621

边栏推荐

猜你喜欢

随机推荐