leetcode103-二叉树的锯齿形层次遍历

原题

给定一个二叉树,返回其节点值的锯齿形层次遍历。(即先从左往右,再从右往左进行下一层遍历,以此类推,层与层之间交替进行)。

例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层次遍历如下:

[
  [3],
  [20,9],
  [15,7] ]

解法

思想

用两个栈来交替存储某一层和下一层的节点:

读取第一个栈的时候,从左向右的读取节点,将它们的子节点从左向右入第二个栈,能使读取第二个栈的时候是以从右向左的顺序出栈的。

读取第二个栈的时候,从右向左的读取节点,将它们的子节点从右向左入第一个栈,能使读取第一个栈的时候是以从左向右的顺序出栈的。

这样交替使用两个栈,可以实现两层之间的顺序反转。

代码

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        Stack<TreeNode> first = new Stack<>();
        Stack<TreeNode> second = new Stack<>();
        List<Integer> cur;
        if(root == null) return ans;
        first.push(root);
        while(!first.isEmpty()||!second.isEmpty()){
            //当前层的节点按从左向右的顺序依次出栈,子节点按从左向右的顺序入second栈,实现顺序逆转
            cur = new ArrayList<>();
            while(!first.isEmpty()){
                TreeNode node = first.pop();
                cur.add(node.val);
                if(node.left!=null) second.push(node.left);
                if(node.right!=null) second.push(node.right);
            }
            ans.add(cur);
            //下一层的节点按从右向左的顺序依次出栈,子节点按从右向左的顺序入first栈,实现顺序逆转
            if(second.isEmpty()) break;
            cur = new ArrayList<>();
            while(!second.isEmpty()){
                TreeNode node = second.pop();
                cur.add(node.val);
                if(node.right!=null) first.push(node.right);
                if(node.left!=null) first.push(node.left);
            }
            ans.add(cur);
        }
        return ans;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode103-%e4%ba%8c%e5%8f%89%e6%a0%91%e7%9a%84%e9%94%af%e9%bd%bf%e5%bd%a2%e5%b1%82%e6%ac%a1%e9%81%8d%e5%8e%86/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月25日
下一篇 2020年1月25日

相关推荐

  • leetcode1071-字符串的最大公因子

    原题 对于字符串 S 和 T,只有在 S = T + ... + T(T 与自身连接 1 次或多次)时,我们才认定 “T 能除尽 S”。 返回最长字符串 X,要求满足 X 能除尽 …

    算法 2020年3月12日
    0250
  • leetcode701-二叉搜索树中的插入操作

    原题 给定二叉搜索树(BST)的根节点和要插入树中的值,将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。 注意,可能存在多种有效的插入方式,只…

    算法 2020年1月16日
    0100
  • leetcode572-另一个树的子树

    原题 给定两个非空二叉树 s 和 t,检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树…

    算法 2020年5月8日
    0380
  • leetcode119-杨辉三角II

    原题 给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。在杨辉三角中,每个数是它左上方和右上方的数的和。 示例: 输入: 3 输出: [1,3,3,1] 进阶: …

    2019年11月22日
    0280
  • leetcode344-反转字符串

    原题 编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组char[]的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间…

    算法 2019年11月18日
    0150
  • leetcode235-二叉搜索树的最近公共祖先

    原题 给定一个二叉二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x …

    2020年1月17日
    0100
  • leetcode55-跳跃游戏

    原题 原题 给定一个非负整数数组,你最初位于数组的第一个位置。 数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个位置。 示例1: 输入: [2,3,1…

    算法 2020年2月9日
    080
  • 剑指offer47-礼物的最大价值

    原题(来源Leetcode) 在一个 m*n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一…

    算法 2020年6月12日
    090
  • leetcode20-有效的括号

    原题 给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序…

    算法 2019年12月11日
    0220
  • leetcode5-最长回文子串

    原题 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有…

    算法 2020年2月20日
    0110

发表回复

登录后才能评论