首页 > 编程语言 >代码随想录算法训练营第十五天| 层序遍历 10 226.翻转二叉树 101.对称二叉树 2

代码随想录算法训练营第十五天| 层序遍历 10 226.翻转二叉树 101.对称二叉树 2

时间:2024-02-07 19:55:06浏览次数:35  
标签:node right TreeNode root 随想录 二叉树 return 第十五天 left

层序遍历  

102. 二叉树的层序遍历 - 力扣(LeetCode)

思路:结合了昨天学到的标记法,每当一层遍历完,向队列中添加一个NULL标记。遍历到NULL节点表示该层遍历完了,将结果存入结果集中。

/**
 * 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:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if (root == NULL)
            return res;
        q.push(root);
        q.push(NULL);
        TreeNode* t;
        vector<int> tmp;
        while (!q.empty()) {
            if (q.front() == NULL) {
                q.pop();
                if (q.empty()) {
                    res.push_back(tmp);
                    break;
                }
                q.push(NULL);
                res.push_back(tmp);
                tmp.clear();
            }
            t = q.front();
            tmp.push_back(t->val);
            if (t->left)
                q.push(t->left);
            if (t->right)
                q.push(t->right);
            q.pop();
        }
        return res;
    }
};

然而这个方法似乎并不够简洁。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector <vector <int>> ret;
        if (!root) {
            return ret;
        }

        queue <TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int currentLevelSize = q.size();
            ret.push_back(vector <int> ());
            for (int i = 1; i <= currentLevelSize; ++i) {
                auto node = q.front(); q.pop();
                ret.back().push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        
        return ret;
    }
};

作者:力扣官方题解
链接:https://leetcode.cn/problems/binary-tree-level-order-traversal/solutions/241885/er-cha-shu-de-ceng-xu-bian-li-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

题目链接:107. 二叉树的层序遍历 II - 力扣(LeetCode)

本题要求反向输出层序遍历,代码不需要变动,别忘了vector可以颠倒。

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        auto levelOrder = vector<vector<int>>();
        if (!root) {
            return levelOrder;
        }
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            auto level = vector<int>();
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                auto node = q.front();
                q.pop();
                level.push_back(node->val);
                if (node->left) {
                    q.push(node->left);
                }
                if (node->right) {
                    q.push(node->right);
                }
            }
            levelOrder.push_back(level);
        }
        reverse(levelOrder.begin(), levelOrder.end());
        return levelOrder;
    }
};

作者:力扣官方题解
链接:https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/solutions/402560/er-cha-shu-de-ceng-ci-bian-li-ii-by-leetcode-solut/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

题目链接:199. 二叉树的右视图 - 力扣(LeetCode)

层序遍历的变体,只需要保存每一层的最后一个就行。

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector <int> ret;
        if (!root) {
            return ret;
        }
        queue <TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int currentLevelSize = q.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                auto node = q.front(); q.pop();
                if(i==currentLevelSize)
                ret.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        
        return ret;
    }

翻转二叉树 

 题目链接:226. 翻转二叉树 - 力扣(LeetCode)

思路:题目不难,还是层序遍历的思想,只要把每个进入队列的节点都转换一下就行了,每个节点只会入队一次,因此也只会转换一次。

class Solution {
public:
    void swap(TreeNode *node){
           if(node->left){
            TreeNode* tmp=node->left;
            node->left=node->right;
            node->right=tmp;
            }
            else{
            TreeNode* tmp=node->right;
            node->right=node->left;
            node->left=tmp;
            }
    }
    TreeNode* invertTree(TreeNode* root) {
        TreeNode* node;
        queue<TreeNode*>q;
        if(root==NULL)return root;
        q.push(root);
        while(!q.empty()){
            node=q.front();
            swap(node);
            if(node->left)q.push(node->left);
            if(node->right)q.push(node->right);
            
            q.pop();
        }

        return root;
    }
};

显然递归法更简洁,没想到竟然能递归自己。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr) {
            return nullptr;
        }
        TreeNode* left = invertTree(root->left);
        TreeNode* right = invertTree(root->right);
        root->left = right;
        root->right = left;
        return root;
    }
};

作者:力扣官方题解
链接:https://leetcode.cn/problems/invert-binary-tree/solutions/415160/fan-zhuan-er-cha-shu-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

对称二叉树 

 思路:简单看了下讲解,自己手写出来了,虽然不是很简洁,但是逻辑清晰。

class Solution {
public:
    bool compare(TreeNode* left,TreeNode*right){
        if(left==NULL&&right==NULL)return true;
        else if(left!=NULL&&right==NULL)return false;
        else if(left==NULL&&right!=NULL)return false;
        else if(left->val!=right->val)return false;
        else {    
            return compare(left->left,right->right)&&compare(left->right,right->left);
        }
    }
    bool isSymmetric(TreeNode* root) {
        if(root==NULL)return true;
        return compare(root->left,root->right);
    }
};

 

这里留一个更简洁的写法,思路一致

class Solution {
public:
    bool check(TreeNode *p, TreeNode *q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};

作者:力扣官方题解
链接:https://leetcode.cn/problems/symmetric-tree/solutions/268109/dui-cheng-er-cha-shu-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

 

标签:node,right,TreeNode,root,随想录,二叉树,return,第十五天,left
From: https://www.cnblogs.com/Liubox/p/18011236

相关文章

  • P2585 [ZJOI2006] 三色二叉树
    原题链接总结1.要学会动态规划这种思维方式,即定义状态和状态之间的转移2.本题的难点在于如何将抽象的输入数据转换成树状结构处理和定义状态,这个定义状态让我想到了初中添加几何线,可能要多做题才能有感觉吧3.有一定模拟的部分,这一部分要细心\(Code\)#include<bits/stdc++.h>......
  • (14/60)二叉树理论基础、递归遍历、迭代遍历、统一迭代
    二叉树理论基础分类满二叉树:只有度为0和度为2的结点,且度为0结点在同一层上(每一层的结点都是满的)。完全二叉树:除了底层外其他层结点都是满的(底层当然也可以是满的),且底层结点从左往右连续不断。二叉搜索树:树的每个结点满足:左子树所有结点值均小于根结点的值右子树所有......
  • 代码随想录 day42 背包问题 分割等和子集
    01背包leetcode没有原题这里是解法importjava.util.Arrays;publicclassBagProblem{publicstaticvoidmain(String[]args){int[]weight={1,3,4};int[]value={15,20,30};intbagSize=4;testWeightBagProblem(weight,value,bagSize);}/***初始化dp......
  • 代码随想录算法训练营第十四天| 理论基础 递归遍历 迭代遍历 统一迭代
    理论基础代码随想录(programmercarl.com)二叉树的链接形式定义(防忘)structTreeNode{intval;TreeNode*left;TreeNode*right;TreeNode(intx):val(x),left(NULL),right(NULL){}};额外补充(关于unordered_map和map)unordered_map和map类似,都是存储......
  • 代码随想录算法训练营第十四天 | 94. 二叉树的中序遍历,144.二叉树的前序遍历,145.二叉
    145.二叉树的后序遍历 已解答简单 相关标签相关企业 给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。 示例1:输入:root=[1,null,2,3]输出:[3,2,1]示例2:输入:root=[]输出:[]示例3:输入:root=[1]输出:[1] 提示:树中节点......
  • 代码随想录算法训练营第十三天 | 59.螺旋矩阵II 209.长度最小的子数组 977.有序数
    977.有序数组的平方 已解答简单 相关标签相关企业 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 示例1:输入:nums=[-4,-1,0,3,10]输出:[0,1,9,16,100]解释:平方后,数组变为[16......
  • 一套模板搞定二叉树算法题--二叉树算法讲解004
    1、二叉树经典习题模拟忘记知识点和技巧时,遇到一个新的二叉树习题,该如何处理思考和写代码解题?1.1、leetcode965题目和题意:题解1成员变量self.ans:题解2递归回传:1.2、leetcode257该题是个经典二叉树题目题目和题意:题解:分析,所有路径,每一个叶子节点都需要到达。到......
  • leedcode 对称二叉树
    迭代法:#Definitionforabinarytreenode.#classTreeNode:#def__init__(self,val=0,left=None,right=None):#self.val=val#self.left=left#self.right=rightclassSolution:defisSymmetric(self,root):......
  • 代码随想录算法训练营第十三天|239. 滑动窗口最大值 347.前 K 个高频元素 总结
    239.滑动窗口最大值题目链接:239.滑动窗口最大值-力扣(LeetCode)给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回 滑动窗口中的最大值 。思路:首先在不考虑......
  • 代码随想录 day41 整数拆分 不同的二叉搜索树
    整数拆分这里的递推式子很不好想一般的想法是dp[i]=max(dp[i],dp[i-j])但是这个式子需要赋值dp[1]=1dp[2]=2dp[3]=3这个不符合dp[i]定义这里递推式子如下dp[i-j]等于拆分成两个或两个以上的数字i*(i-j)就是两个数字拆分不同的二叉搜索树难点依旧是递推式是怎么......