[LintCode/LeetCode] Binary Tree Zigzag Level Orde

AlphaGooo 发布于2019-08-14 15:40 / 2595人阅读

Problem

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).

Example

Given binary tree {3,9,20,#,#,15,7},

return its zigzag level order traversal as:

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

Note Solution

public class Solution {
    public ArrayList> zigzagLevelOrder(TreeNode root) {
        ArrayList> res = new ArrayList();
        if (root == null) return res;
        boolean LR = true;
        Stack stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            Stack curStack = new Stack();
            ArrayList curList = new ArrayList();
            while (!stack.isEmpty()) {
                TreeNode cur = stack.pop();
                curList.add(cur.val);
                if (LR) {
                    if (cur.left != null) curStack.push(cur.left);
                    if (cur.right != null) curStack.push(cur.right);
                }
                else {
                    if (cur.right != null) curStack.push(cur.right);
                    if (cur.left != null) curStack.push(cur.left);
                }
            }
            stack = curStack;
            res.add(curList);
            LR = !LR;
        }
        return res;
    }
}

私有云混合云 binary-tree binary-search-tree Zigzag Binary

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65928.html

[LintCode/LeetCode] Binary Tree Level Order Traver

Problem 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 / ...

makeFoxPlay 2019-08-14 15:48 评论0 收藏0
[Leetcode] Binary Tree Traversal 二叉树遍历

摘要：栈迭代复杂度时间空间递归栈空间对于二叉树思路用迭代法做深度优先搜索的技巧就是使用一个显式声明的存储遍历到节点，替代递归中的进程栈，实际上空间复杂度还是一样的。对于先序遍历，我们出栈顶节点，记录它的值，然后将它的左右子节点入栈，以此类推。 Binary Tree Preorder Traversal Given a binary tree, return the preorder tr...

RaoMeng 2019-08-14 12:25 评论0 收藏0
[LintCode/LeetCode] Balanced Binary Tree

摘要：根据二叉平衡树的定义，我们先写一个求二叉树最大深度的函数。在主函数中，利用比较左右子树的差值来判断当前结点的平衡性，如果不满足则返回。 Problem Given a binary tree, determine if it is height-balanced. For this problem, a height-balanced binary tree is defined as...

morgan 2019-08-14 15:33 评论0 收藏0
[LintCode/LeetCode] Binary Tree Pruning

Problem Binary Tree PruningWe are given the head node root of a binary tree, where additionally every nodes value is either a 0 or a 1. Return the same tree where every subtree (of the given tree) not...

rockswang 2019-08-16 12:37 评论0 收藏0
[LintCode/LeetCode] Construct Binary Tree from Tr

摘要：做了几道二分法的题目练手，发现这道题已经淡忘了，记录一下。这道题目的要点在于找的区间。边界条件需要注意若或数组为空，返回空当前进到超出末位，或超过，返回空每次创建完根节点之后，要将加，才能进行递归。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...

马忠志 2019-08-14 15:40 评论0 收藏0