LeetCode | Binary Tree Zigzag Level Order Traversal

2024-08-25 18:08

本文主要是介绍LeetCode | Binary Tree Zigzag Level Order Traversal,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

二叉树Z型输出

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

其实还是广度优先遍历,只不过这里对偶数行需要reverse一下,
发现stl可以方便地完成reverse(row.begin(),row.end())即可

然后也要注意这类题目需要知道递归的怎么写。
其实递归就是传入一个level来判断当前进入到了第几层,然后再将数据存入到这一层中

class Solution {
public://递归版本vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int> > result;tranverse(root,0,result);for(int i=0;i<result.size();i++)if(i&0x01) reverse(result[i].begin(),result[i].end());return result;}void tranverse(TreeNode* root,int level,vector<vector<int> > &result){if(root==NULL) return;if(level>=result.size())result.push_back(vector<int> ());result[level].push_back(root->val);tranverse(root->left,level+1,result);tranverse(root->right,level+1,result);}//非递归版
//     vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
//         vector<vector<int> > result; 
//      if(!root) return result;
//      queue<TreeNode*> Q;
//      Q.push(root);//      int count=0;
//      while(!Q.empty()){
//          queue<TreeNode*> Qnext;
//          vector<int> row;
//          while(!Q.empty()){
//              TreeNode* node=Q.front();
//              Q.pop();//              row.push_back(node->val);//              if(node->left) Qnext.push(node->left);
//              if(node->right) Qnext.push(node->right);
//          }
//          if(count & 0x01) reverse(row.begin(),row.end());
//          result.push_back(row);
//          Q=Qnext;
//          count++;
//      }
//      return result;
//     }
};

字符串Z型输出——原题

上面的题是由这道题演化而来的
The string “PAYPALISHIRING” is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

P A H N
A P L S I I G
Y I R
And then read line by line: “PAHNAPLSIIGYIR”
Write the code that will take a string and make this conversion given a number of rows:

string convert(string text, int nRows);
convert(“PAYPALISHIRING”, 3) should return “PAHNAPLSIIGYIR”.

题意很简单,很像之前让自己排列并输出一些数据

于是主要就是找规律了~

class Solution {
public:string convert(string s, int numRows) {int n=s.size();if(n<=1) return s;if(numRows<=1) return s;string target="";for(int i=0;i<numRows;i++){for(int j=i,count=1;j<n;j+=2*numRows-2,count++){target=target+s[j];if(j+(numRows-i-1)*2<n && i>0 && i>0 && i<numRows-1)target=target+s[j+(numRows-i-1)*2];}}return target;}
};

这篇关于LeetCode | Binary Tree Zigzag Level Order Traversal的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1106280

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

uva 575 Skew Binary(位运算)

求第一个以(2^(k+1)-1)为进制的数。 数据不大,可以直接搞。 代码: #include <stdio.h>#include <string.h>const int maxn = 100 + 5;int main(){char num[maxn];while (scanf("%s", num) == 1){if (num[0] == '0')break;int len =

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

树(Tree)——《啊哈!算法》

树 什么是树?树是一种特殊的图,不包含回路的连通无向树。 正因为树有着“不包含回路”这个特点,所以树就被赋予了很多特性。 一棵树中的任意两个结点有且仅有唯一的一条路径连通。一棵树如果有n个结点,那么它一定恰好有n-1条边。在一棵树中加一条边将会构成一个回路。 一棵树有且只有一个根结点。 没有父结点的结点称为根结点(祖先)。没有子结点的结点称为叶结点。如果一个结点既不是根结点也不是叶

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划