首页 > 编程语言 >算法随想Day13【二叉树】| LC102-二叉树的层次遍历(系列题目)、LC226-翻转二叉树、LC101-对称二叉树

算法随想Day13【二叉树】| LC102-二叉树的层次遍历(系列题目)、LC226-翻转二叉树、LC101-对称二叉树

时间:2023-02-15 23:11:56浏览次数:42  
标签:LC101 Node LC102 curr val que 二叉树 root

二叉树层次遍历的相关题目

  • 102.二叉树的层序遍历
  • 107.二叉树的层次遍历II
  • 199.二叉树的右视图
  • 637.二叉树的层平均值
  • 429.N叉树的层序遍历
  • 515.在每个树行中找最大值
  • 116.填充每个节点的下一个右侧节点指针
  • 117.填充每个节点的下一个右侧节点指针II
  • 104.二叉树的最大深度
  • 111.二叉树的最小深度

LC102. 二叉树的层次遍历

vector<vector<int>> levelOrder(TreeNode* root)
{
    int size  = 0;
    vector<vector<int>> result;
    vector<int> temp;
    TreeNode* curr = nullptr;
    queue<TreeNode*> que;
    if (root != nullptr)
    {
        que.push(root);
    }
    while (que.empty() != true)
    {
        size = que.size();
        for (int i = 0; i < size; ++i)
        {
            curr = que.front();
            temp.push_back(curr->val);
            que.pop();
            if (curr->left != nullptr) que.push(curr->left);
            if (curr->right != nullptr) que.push(curr->right);
        }
        result.push_back(temp);
        temp.clear();
    }

    return result;
}

LC107. 二叉树的层次遍历Ⅱ

LC102的基础上,在return前,对resul进行reverse:reverse(result.begin(), right.end));

LC199. 二叉树的右视图

LC102的基础上,在for循环中当i = size - 1时,把当前元素push如vector result中

LC637. 二叉树的层平均值

LC102的基础上,在for循环中,统计该层所有数之和sum += curr->val,for后result.push(sum / size)

LC429. N 叉树的层序遍历

和LC102的思路一模一样,只不过数据结构的包装变换了下

class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};

class Solution
{
public:
    vector<vector<int>> levelOrder(Node* root)
    {
        int size  = 0;
        vector<vector<int>> result;
        vector<int> temp;
        Node* curr = nullptr;
        queue<Node*> que;
        if (root != nullptr)
        {
            que.push(root);
        }
        while (que.empty() != true)
        {
            size = que.size();
            for (int i = 0; i < size; ++i)
            {
                curr = que.front();
                temp.push_back(curr->val);
                que.pop();
                for (int i = 0; i < curr->children.size(); ++i)
                {
                    que.push(curr->children[i]);
                }
            }
            result.push_back(temp);
            temp.clear();
        }

        return result;
    }
};

LC515. 在每个树行中找最大值

在LC102的基础上,在每行的遍历for中找max值,max = curr->val > max ? curr->val : max

LC116. 填充每个节点的下一个右侧节点指针

LC102的层次遍历思路,换下包装,缝缝补补再用一阵。

class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};

class Solution
{
public:
    Node* connect(Node* root)
    {
        int size  = 0;
        vector<vector<int>> result;
        vector<int> temp;
        Node* curr = nullptr;
        queue<Node*> que;
        if (root != nullptr)
        {
            que.push(root);
        }
        while (que.empty() != true)
        {
            size = que.size();
            for (int i = 0; i < size; ++i)
            {
                curr = que.front();
                que.pop();
                if(curr->left != nullptr) que.push(curr->left);
                if(curr->right != nullptr) que.push(curr->right);
                if (i == size - 1)
                {
                    curr->next = nullptr;
                    break;
                }
                curr->next = que.front();
            }
        }

        return root;
    }
};

LC117. 填充每个节点的下一个右侧节点指针 II

这道题目说是二叉树,但116题目说是完整二叉树,其实没有任何差别,一样的代码一样的逻辑一样的味道

后面再补充下LC116,LC117的递归实现方法

LC104. 二叉树的最大深度

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数

在LC102的基础上,定义一个变量depth,每进入一次for循环,depth++即可

LC111. 二叉树的最小深度

在LC102的基础上,记录当前for遍历的是第几层,一旦在某层中,第一次出现curr->left == nullptr && curr->right == nullptr时,即可返回当前层数为最小深度

LC226. 翻转二叉树

很自然而然地写出了,递归的方法。

但也是在看了Carl哥的视频讲解后,才知道这是一个前序遍历(中左右)的思想,左中右可以代表如下三句。

所以自己在写这道题时,也不清楚每句代表的含义。这道题用后序的做法也是可以的,即调整下三句为左右中。

但此处中序遍历的左中右是不行的,模拟下,root的左子树内部翻转完了,回溯到root,此时对左右子树又来一次翻转,此时对root来说,原来的左右子树整体发生了翻转,下面又对右子树的内部进行翻转,而此时的右子树是上一步翻转前的左子树,所以所谓“左”,“右”,其实都是对源树的左子树内部做翻转,起不到效果。如果非得写成“左中右”的形式的话,那如下两句“左”,“右”,都应该写为“invertTree(root->left);”

TreeNode* invertTree(TreeNode* root)
{
    if (root == nullptr)
    {
        return root;
    }
    swap(root->left, root->right);  //中
    invertTree(root->left);  //左
    invertTree(root->right);  //右
    return root;
}

自己再用层次遍历方法实现的迭代法

TreeNode* invertTree_iteration(TreeNode* root)
{
    TreeNode* curr = nullptr;
    queue<TreeNode*> que;
    if (root != nullptr)
    {
        que.push(root);
    }
    while (que.empty() != true)
    {
        curr = que.front();
        que.pop();
        swap(curr->left, curr->right);
        if (curr->left != nullptr) que.push(curr->left);
        if (curr->right != nullptr) que.push(curr->right);
    }

    return root;
}

LC101. 对称二叉树

开始自己的想法是,在LC102二叉树层次遍历的基础上,用deque去代替queue模拟队列,做push和pop操作,不同的是应用deque的优势,在每层的节点访问中,应用下标访问,进行由外侧往里侧移动的判断(若该层的节点数size()不为偶数,直接返回false,当然不包括首层)

标签:LC101,Node,LC102,curr,val,que,二叉树,root
From: https://www.cnblogs.com/Mingzijiang/p/17125125.html

相关文章

  • 二叉树的最小深度
    给定一个二叉树,找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明:叶子节点是指没有子节点的节点。示例1:输入:root=[3,9,20,null,null......
  • 104. 二叉树的最大深度
    题目描述给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明:叶子节点是指没有子节点的节点。方法1深度优先搜索描述......
  • 从上至下遍历二叉树---队列的性质
    问题:从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。剑指Offer32-I.从上到下打印二叉树-力扣(LeetCode)思路:利用队列先入先出的性质,可以依次打......
  • 算法随想Day12【二叉树】| LC144、LC145、LC94-二叉树的前中后序遍历
    LC144、LC145、LC94-二叉树的前中后遍历二叉树递归遍历比较容易实现二叉树非递归遍历迭代法需要通过使用“栈”来模拟递归的过程前序遍历:放入root节点,弹出每个节点时......
  • 算法刷题-二叉树的锯齿形层序遍历、用栈实现队列_栈设计、买卖股票的最佳时机 IV
    二叉树的锯齿形层序遍历(树、广度优先搜索)给定一个二叉树,返回其节点值的锯齿形层序遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。例如:给定二......
  • 基于二叉树的高效IP检索格式MMDB
     一、MMDB简介MMDB(MaxMindDatabase)是MaxMind推出的一个数据存储和检索的数据库格式,用于旗下针对IP检索和存储的Geo产品。IP格式由二进制比特数组组成,很容易想到每......
  • L2-011 玩转二叉树 (25 分)
    L2-011 玩转二叉树 (25分)给定一棵二叉树的中序遍历和前序遍历,请你先将树做个镜面反转,再输出反转后的层序遍历的序列。所谓镜面反转,是指将所有非叶结点的左右孩子对换......
  • 剑指 Offer 32 - III. 从上到下打印二叉树 III(java解题)
    目录1.题目2.解题思路3.数据类型功能函数总结4.java代码从上到下打印二叉树系列题目1.剑指Offer32-I.从上到下打印二叉树(java解题)2.剑指Offer32-II.从上......
  • 判断二叉树是否为平衡二叉树
    问题:判断二叉树是否为平衡二叉树面试题55-II.平衡二叉树(从底至顶、从顶至底,清晰图解)-平衡二叉树-力扣(LeetCode)方法一:后序遍历+剪枝,自下而上后续遍历节点,递归向上......
  • leetcode144-二叉树的前序遍历
    leetcode144-二叉树的前序遍历​​1、问题描述​​​​2、递归解法​​1、问题描述  给你二叉树的根节点​​root​​,返回它节点值的前序遍历。  示例1:输入:root=[......