C++实现LeetCode(103.二叉树的之字形层序遍历)

[LeetCode] 103. Binary Tree Zigzag Level Order Traversal 二叉树的之字形层序遍历

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]
]

这道二叉树的之字形层序遍历是之前那道 Binary Tree Level Order Traversal 的变形,不同之处在于一行是从左到右遍历,下一行是从右往左遍历,交叉往返的之字形的层序遍历。最简单直接的方法就是利用层序遍历,并使用一个变量 cnt 来统计当前的层数(从0开始),将所有的奇数层的结点值进行翻转一下即可,参见代码如下:

解法一:

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> res;
        queue<TreeNode*> q{{root}};
        int cnt = 0;
        while (!q.empty()) {
            vector<int> oneLevel;
            for (int i = q.size(); i > 0; --i) {
                TreeNode *t = q.front(); q.pop();
                oneLevel.push_back(t->val);
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            if (cnt % 2 == 1) reverse(oneLevel.begin(), oneLevel.end());
            res.push_back(oneLevel);
            ++cnt;
        }
        return res;
    }
};

我们可以将上面的解法进行优化一下,翻转数组虽然可行,但是比较耗时,假如能够直接计算出每个结点值在数组中的坐标,就可以直接进行更新了。由于每层的结点数是知道的,就是队列的元素个数,所以可以直接初始化数组的大小。此时使用一个变量 leftToRight 来标记顺序,初始时是 true,当此变量为 true 的时候,每次加入数组的位置就是i本身,若变量为 false 了,则加入到 size-1-i 位置上,这样就直接相当于翻转了数组。每层遍历完了之后,需要翻转 leftToRight 变量,同时不要忘了将 oneLevel 加入结果 res,参见代码如下:

解法二:

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if (!root) return {};
        vector<vector<int>> res;
        queue<TreeNode*> q{{root}};
        bool leftToRight = true;
        while (!q.empty()) {
            int size = q.size();
            vector<int> oneLevel(size);
            for (int i = 0; i < size; ++i) {
                TreeNode *t = q.front(); q.pop();
                int idx = leftToRight ? i : (size - 1 - i);
                oneLevel[idx] = t->val;
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            leftToRight = !leftToRight;
            res.push_back(oneLevel);
        }
        return res;
    }
};

我们也可以使用递归的方法来解,这里实际上用的是先序遍历,递归函数需要一个变量 level 来记录当前的深度,由于 level 是从0开始的,假如结果 res 的大小等于 level,就需要在结果 res 中新加一个空集,这样可以保证 res[level] 不会越界。取出 res[level] 之后,判断 levle 的奇偶,若其为偶数,则将 node->val 加入 oneLevel 的末尾,若为奇数,则加在 oneLevel 的开头。然后分别对 node 的左右子结点调用递归函数,此时要传入 level+1 即可,参见代码如下:

解法三:

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        helper(root, 0, res);
        return res;
    }
    void helper(TreeNode* node, int level, vector<vector<int>>& res) {
        if (!node) return;
        if (res.size() <= level) {
            res.push_back({});
        }
        vector<int> &oneLevel = res[level];
        if (level % 2 == 0) oneLevel.push_back(node->val);
        else oneLevel.insert(oneLevel.begin(), node->val);
        helper(node->left, level + 1, res);
        helper(node->right, level + 1, res);
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/103

类似题目:

Binary Tree Level Order Traversal

参考资料:

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/discuss/33815/My-accepted-JAVA-solution

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/discuss/33825/c%2B%2B-5ms-version%3A-one-queue-and-without-reverse-operation-by-using-size-of-each-level

到此这篇关于C++实现LeetCode(103.二叉树的之字形层序遍历)的文章就介绍到这了,更多相关C++实现二叉树的之字形层序遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-07-21

C++实现LeetCode(99.复原二叉搜索树)

[LeetCode] 99. Recover Binary Search Tree 复原二叉搜索树 Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure. Example 1: Input: [1,3,null,null,2]    1 / 3 \ 2 Output: [3,1,null,null,2]    3 / 1

C++实现LeetCode(97.交织相错的字符串)

[LeetCode] 97.Interleaving String 交织相错的字符串 Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2. Example 1: Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true Example 2: Input: s1 = &quo

C++实现LeetCode(102.二叉树层序遍历)

[LeetCode] 102. Binary Tree Level Order Traversal 二叉树层序遍历 Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree {3,9,20,#,#,15,7},     3 / \ 9  20 /  \ 15 

C++实现LeetCode(98.验证二叉搜索树)

[LeetCode] 98. Validate Binary Search Tree 验证二叉搜索树 Given a binary tree, determine if it is a valid binary search tree (BST). Assume a BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The ri

C++实现LeetCode(145.二叉树的后序遍历)

[LeetCode] 145. Binary Tree Postorder Traversal 二叉树的后序遍历 Given a binary tree, return the postorder traversal of its nodes' values. For example: Given binary tree {1,#,2,3},    1 \ 2 / 3 return [3,2,1]. Note: Recursive solution is trivial, could you d

C++实现LeetCode(100.判断相同树)

[LeetCode] 100. Same Tree 判断相同树 Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. Example 1: Input:     1     

C++实现LeetCode(107.二叉树层序遍历之二)

[LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历之二 Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root). Example 1: Input: root = [3

C++实现LeetCode(312.打气球游戏)

[LeetCode] 312. Burst Balloons 打气球游戏 Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon iyou will get nums[left] * nums[i]

C++实现LeetCode(139.拆分词句)

[LeetCode] 139. Word Break 拆分词句 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Note: The same word in the dic

python 输入字符串生成所有有效的IP地址(LeetCode 93号题)

这题的官方难度是Medium,点赞1296,反对505,通过率35.4%.从各项指标来说看起来有些中规中矩,实际上也的确如此.这道题的解法和立意都有些显得新意不足,但总体来说题目的质量还是可以的,值得一做. 题意 给定一个由数字组成的字符串,我们希望通过这个字符串得到所有有效ip地址的组合.对于一个有效的ip地址而言,它应该有4个数字组成,每一个数字的范围在0到255之间. 一个字符串可能可以转化成多个ip地址,我们需要存储下来所有可以成立的情况. 样例 Input: "25525511135&

使用BAT命令关闭:135端口、139端口、445端口等

都知道135端口,139端口以及445端口.这三个端口容易被黑客或者病毒利用.所以我们今天就来教下大家如何关闭它. 太难的方法就不教给大家了.什么实用策略组之类的.新手感觉很麻烦.所以下面给大家来简单的教程 打开可以将下面的代码复制到文本里面然后保存为123.bat,然后运行就可以了 @echo off gpupdate >nul rem For Client only iPseccmd -w REG -p "HFUT_SECU" -o -x >nul ipseccmd -

Oracle数据行拆分多行方法示例

工作和学习中常常会遇到一行要分割成多行数据的情况,在此整理一下做下对比. 单行拆分 如果表数据只有一行,则可以直接在原表上直接使用connect by+正则的方法,比如: select regexp_substr('444.555.666', '[^.]+', 1, level) col from dual connect by level <= regexp_count('444.555.666', '\.') + 1 输出结果: COL ---- 444 555 666 多行拆分 如果数据表

LeetCode -- Path Sum III分析及实现方法

LeetCode -- Path Sum III分析及实现方法 题目描述: You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards

使用perl实现拆分数据表(mysql)并迁移数据实例

随着业务量的增长,可能需要对表进行拆分来提高性能. 下面这个例子是将www.jb51.net的users表拆分成10个表ttlsa_user_0-ttlsa_user_9. 拆分迁移数据程序如下所示: 1.创建ttlsa_user_0-ttlsa_user_9表 复制代码 代码如下: #!/usr/bin/perl ################################### ### author: www.jb51.net ### ### QQ群:232608061  ### ###

MySQL截取和拆分字符串函数用法示例

本文实例讲述了MySQL截取和拆分字符串函数用法.分享给大家供大家参考,具体如下: 首先说截取字符串函数: SUBSTRING(commentid,9) 这个很简单,从第9个字符开始截取到最后.SUBSTRING的参数有三个,最后一个是截取的长度,默认是到结尾,负数是倒数第几位. 接着说拆分字符串函数: SUBSTRING_INDEX(commentid, '-', 1) 这个就稍稍复杂一些了,他的意思是以 - 进行拆分字符串,从第一个关键词开始取前面所有的字符串.如果上面的第三个参数修改为 -

将一个数组按照固定大小进行拆分成数组的方法

如下所示: /** * ArraySplit.java * Copyright(C) 2014 */ package com.udpdemo.test2; import java.util.ArrayList; import java.util.List; /** * * @author cuiran * @version 1.0.0 */ public class ArraySplit { /** * @param args * */ public static void main(Strin

php 操作数组(合并,拆分,追加,查找,删除等)

1. 合并数组 array_merge()函数将数组合并到一起,返回一个联合的数组.所得到的数组以第一个输入数组参数开始,按后面数组参数出现的顺序依次迫加.其形式为: 复制代码 代码如下: array array_merge (array array1 array2-,arrayN) 这个函数将一个或多个数组的单元合并起来,一个数组中的值附加在前一个数组的后面.返回作为结果的数组. 如果输入的数组中有相同的字符串键名,则该键名后面的值将覆盖前一个值.然而,如果数组包含数字键名,后面的值将不会覆盖

Python实现简单拆分PDF文件的方法

本文实例讲述了Python实现简单拆分PDF文件的方法.分享给大家供大家参考.具体如下: 依赖pyPdf处理PDF文件 切分pdf文件 使用方法: 1)将要切分的文件放在input_dir目录下 2)在configure.txt文件中设置要切分的份数(如要切分4份,则设置part_num=4) 3)执行程序 4)切分后的文件保存在output_dir目录下 5)运行日志写在pp_log.txt中 P.S. 本程序可以批量切割多个pdf文件 from pyPdf import PdfFileWri

javascript字符串拆分成单个字符相加和不超过10,求最终值第1/2页

首先把你的生日列出来 比如 1987 12 25 然后一位位的相加 1+9+8+7+1+2+2+5=35 把得出的数字再拆分 再加 3+5=8 得出的数字8 就是最后的结果,如果超过10的话就在拆分再加 1 肾脏 2 眼睛 3 才华天赋 4 良性基因 5 友情 6 慈善之心 7 亲情 8 健康和寿命 9 爱情 10 恭喜你 你拥有纯净的灵魂 最适合典当cloeft的示例 var str = "19871229"; var count = 0; for(var i = 0 ; i 10)