首页 > 其他分享 >(15/60)层序遍历、翻转二叉树、对称二叉树

(15/60)层序遍历、翻转二叉树、对称二叉树

时间:2024-02-07 21:23:18浏览次数:26  
标签:right TreeNode val 层序 que 二叉树 15 root left

层序遍历

leetcode:

102.二叉树的层序遍历

思路

  1. root如果非空就入队

  2. 队列不空时,循环:

    • 开头记录当前队列size

    • 循环size次:

      • 取队首结点,队首出队;
      • 本层元素数组vec记录node->val
      • (判断非空)左、右孩子入队

复杂度分析

时间复杂度:O(N)。

空间复杂度:O(N)。

注意点

代码实现

/**
 * 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>> result;
        queue<TreeNode*> que;
        if(root != NULL) que.push(root);

        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            while(size--){
                TreeNode* node = que.front(); que.pop();
                vec.push_back(node->val);
                if(node->left)  que.push(node->left);
                if(node->right) que.push(node->right);
            }
            result.push_back(vec);
        }

        return result;
    }
};

429. N叉树的层序遍历

思路

层序遍历基础上,左、右结点入队改为遍历children数组的元素入队。

复杂度分析

时间复杂度:O(N)。

空间复杂度:O(N)。

注意点

代码实现

/*
// Definition for a Node.
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) {
        vector<vector<int>> result;
        queue<Node*> que;
        if(root != NULL) que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            while(size--){
                Node* node = que.front(); que.pop();
                vec.push_back(node->val);
                for(Node* node : node->children){
                    if(node != NULL) que.push(node);
                }
            }
            result.push_back(vec);
        }

        return result;
    }
};

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

思路

层序遍历基础上,若非该层最后一个结点:取队首结点nextNode,next->next = nextNode;否则next->next = NULL

复杂度分析

时间复杂度:O(N)。

空间复杂度:O(N)。

注意点

代码实现

/*
// Definition for a Node.
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) {
        queue<Node*> que;
        if(root != NULL) que.push(root);
        while(!que.empty()){
            int size = que.size();
            for(int i = 0;i < size;i++){
                Node* node = que.front(); que.pop();
                if(i == size - 1) node->next = NULL;
                else{
                    Node* nextNode = que.front();
                    node->next = nextNode;
                }
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }

        return root;
    }
};

111. 二叉树的最小深度

思路

左右子结点都为NULL的就是叶子结点。又因为是层序遍历,第一个碰到的叶子结点就是最浅的叶子结点。

复杂度分析

时间复杂度:O(N)。

空间复杂度:O(N)。

注意点

代码实现

/**
 * 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:
    int minDepth(TreeNode* root) {
        int minD = INT32_MAX;
        int count = 0;
        queue<TreeNode*> que;
        if(root != NULL) que.push(root);
        while(!que.empty()){
            int size = que.size();
            count++;
            while(size--){
                TreeNode* node = que.front(); que.pop();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
                // 左、右结点都为空时就是叶子结点
                // 因为是层序遍历,在第一次遇见叶子时就是最小深度
                if(!node->left && !node->right) return count; 
            }
        }

        return 0;
    }
};

翻转二叉树

leetcode:226. 翻转二叉树

前序、后序遍历

思路

同递归遍历,把数组记录那步改为交换。

复杂度分析

时间复杂度:O(N)。

空间复杂度:O(N)。

注意点

代码实现

/**
 * 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:
    void reverseTree(TreeNode* root){
        if(root == NULL) return;
        swap(root->left,root->right);	// 根
        reverseTree(root->left);	// 左
        reverseTree(root->right);	// 右
    }
    TreeNode* invertTree(TreeNode* root) {
        reverseTree(root);
        return root;
    }
};

中序遍历

思路

中序翻转后原来的左右互换了,因此要左、根、左。

复杂度分析

时间复杂度:O(N)。

空间复杂度:O(N)。

注意点

代码实现

/**
 * 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:
    void reverseTree(TreeNode* root){
        if(root == NULL) return;
        reverseTree(root->left);	// 左
        swap(root->left,root->right);	// 根
        reverseTree(root->left);	// 左
    }
    TreeNode* invertTree(TreeNode* root) {
        reverseTree(root);
        return root;
    }
};

对称二叉树

递归法

思路

递归三部曲

  1. 返回值bool,传入参数:左结点、右结点。
  2. 退出条件:
    • 左空右不空 false
    • 左不空右空 false
    • 左右都不空且值不相等 false
    • 左右都空 true
  3. 单层递归逻辑:
    • 处理外层
    • 处理内层
    • 处理根结点

复杂度分析

时间复杂度:

空间复杂度:

注意点

前、中、后序主要取决于处理中间结点的时机,不一定是先左后右。此处就是先处理外层,再处理内层。

代码实现

/**
 * 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 compare(TreeNode* left,TreeNode* right){
        if( ( !left && right ) ||	// 左空右不空
            ( left && !right ) ||	// 左不空右空
            ( (left && right) && (left->val != right->val) ) // 左右都不空且值不等
        )
            return false;
        else if(!left && !right) return true;	// 左右都空->对称
        bool outside = compare(left->left,right->right);
        bool inside = compare(left->right,right->left);
        
        return outside && inside;
    }

    bool isSymmetric(TreeNode* root) {
        return compare(root->left,root->right);
    }
};

标签:right,TreeNode,val,层序,que,二叉树,15,root,left
From: https://www.cnblogs.com/tazdingo/p/18011310

相关文章

  • 代码随想录算法训练营第十五天| 层序遍历 10 226.翻转二叉树 101.对称二叉树 2
    层序遍历  102.二叉树的层序遍历-力扣(LeetCode)思路:结合了昨天学到的标记法,每当一层遍历完,向队列中添加一个NULL标记。遍历到NULL节点表示该层遍历完了,将结果存入结果集中。/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNo......
  • P2585 [ZJOI2006] 三色二叉树
    原题链接总结1.要学会动态规划这种思维方式,即定义状态和状态之间的转移2.本题的难点在于如何将抽象的输入数据转换成树状结构处理和定义状态,这个定义状态让我想到了初中添加几何线,可能要多做题才能有感觉吧3.有一定模拟的部分,这一部分要细心\(Code\)#include<bits/stdc++.h>......
  • Go语言精进之路读书笔记第15条——了解string实现原理并高效使用
    15.1Go语言的字符串类型在Go语言中,无论是字符串常量、字符串变量还是代码中出现的字符串字面量,它们的类型都被统一设置为string特点string类型的数据是不可变的对string进行切片化后,Go编译器会为切片变量重新分配底层存储而不是共用string的底层存储string的底层的数据存......
  • 【洛谷 P2670】[NOIP2015 普及组] 扫雷游戏 题解(模拟)
    [NOIP2015普及组]扫雷游戏题目背景NOIP2015普及组T2题目描述扫雷游戏是一款十分经典的单机小游戏。在行列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。玩家翻开一个非地雷格时,该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的......
  • 面试经典 150 题 (十四)
    就用除法classSolution{publicint[]productExceptSelf(int[]nums){int[]answer=newint[nums.length];intsum=1;intzeroNum=0;for(inti=0;i<nums.length;i++){if(nums[i]==0)zeroNum++;......
  • 面试经典 150 题 (十三)
    先来个大的classRandomizedSet{privateHashSet<Integer>hashSet;publicRandomizedSet(){hashSet=newHashSet<Integer>();}publicbooleaninsert(intval){if(hashSet.contains(val)){returnfa......
  • 网工内推 | 高级网工,IE认证优先,最高15K,五险一金
    01丰沃创新(北京)科技有限公司招聘岗位:高级网络工程师职责描述:1.主要负责移动营运商数据中心机房网络的维护工作;2.负责防火墙策略调整,负责交换机路由器等网络设备的配置;3.负责云专线的入网配置;4.负责处理网络突发状况,例如卡顿、环路、网络通讯断开等问题;5.其他项目经理安排的......
  • 面试经典 150 题 (十二)
    排序,i代表至少发表的论文数量时间复杂度:O(nlogn)空间复杂度:O(logn)classSolution{publicinthIndex(int[]citations){//01356intlength=citations.length;Arrays.sort(citations);inth=0;for(inti=1......
  • CF1415E New Game Plus! 题解
    解题思路简单贪心题,我们可以把整个序列看作\(k+1\)个可重集,首先可以得到一个显然的结论:较大的数一定比较小的数先放入一个集合中。同样,由于每一轮\(ans\getsans+\maxsum_i\),其中\(sum_i\)表示第\(i\)个集合的元素和,那么,我们一定会将当前的元素放入当前和最大的哪个集合......
  • #排列组合#CF1550D Excellent Arrays
    洛谷传送门CF1550D分析对于excellent的\(a\)来说\(|a_i-i|=x\)的值是固定的,考虑枚举它一半正一半负时函数值是最大的,当\(n\)为奇数时要分为两种情况(不过可以通过杨辉三角合并)问题是,由于\(l,r\)的范围,并不能做到所有位置都能可正可负,不过不超过\(mn=\min\{1-l,r-n\}......