[LintCode/LeetCode] Binary Tree Zigzag Level Orde

AlphaGooo 發(fā)布于2019-08-14 15:40 / 2764人閱讀

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;
    }
}

云服務器 GPU云服務器 binary-tree binary-search-tree Zigzag Binary

文章版權歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.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 二叉樹遍歷

摘要：棧迭代復雜度時間空間遞歸棧空間對于二叉樹思路用迭代法做深度優(yōu)先搜索的技巧就是使用一個顯式聲明的存儲遍歷到節(jié)點，替代遞歸中的進程棧，實際上空間復雜度還是一樣的。對于先序遍歷，我們出棧頂節(jié)點，記錄它的值，然后將它的左右子節(jié)點入棧，以此類推。 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

摘要：根據(jù)二叉平衡樹的定義，我們先寫一個求二叉樹最大深度的函數(shù)。在主函數(shù)中，利用比較左右子樹的差值來判斷當前結(jié)點的平衡性，如果不滿足則返回。 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

摘要：做了幾道二分法的題目練手，發(fā)現(xiàn)這道題已經(jīng)淡忘了，記錄一下。這道題目的要點在于找的區(qū)間。邊界條件需要注意若或數(shù)組為空，返回空當前進到超出末位，或超過，返回空每次創(chuàng)建完根節(jié)點之后，要將加，才能進行遞歸。 Construct Binary Tree from Inorder and Preorder Traversal Problem Given preorder and inorder t...

馬忠志 2019-08-14 15:40 評論0 收藏0