久久精品中文字幕av,av.涩涩涩涩涩涩涩涩,亚洲国产日韩欧美精品成人久久久,成人福利电影免费在线观看,日产国产原创av,日韩av午夜激情,bt天堂中文字幕,超级碰人妻在线视频,欧美老熟妇久久一区二区

# Binary Tree Zigzag Level Order Traversal ### Source - leetcode: [Binary Tree Zigzag Level Order Traversal | LeetCode OJ](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/) - lintcode: [(71) Binary Tree Zigzag Level Order Traversal](http://www.lintcode.com/en/problem/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). Example Given binary tree {3,9,20,#,#,15,7}, 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ] ~~~ ### 題解1 - 隊(duì)列 二叉樹的廣度優(yōu)先遍歷使用隊(duì)列非常容易實(shí)現(xiàn)，這道題要求的是蛇形遍歷，我們可以發(fā)現(xiàn)奇數(shù)行的遍歷仍然可以按照廣度優(yōu)先遍歷的方式實(shí)現(xiàn)，而對(duì)于偶數(shù)行，只要翻轉(zhuǎn)一下就好了。 ### Java ~~~ /** * Definition of TreeNode: * public class TreeNode { * public int val; * public TreeNode left, right; * public TreeNode(int val) { * this.val = val; * this.left = this.right = null; * } * } */ public class Solution { /** * @param root: The root of binary tree. * @return: A list of lists of integer include * the zigzag level order traversal of its nodes' values */ public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) { ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>(); if (root == null) return result; boolean odd = true; Queue<TreeNode> q = new LinkedList<TreeNode>(); q.offer(root); while (!q.isEmpty()) { // level traversal int qLen = q.size(); ArrayList<Integer> level = new ArrayList<Integer>(); for (int i = 0; i < qLen; i++) { TreeNode node = q.poll(); level.add(node.val); if (node.left != null) q.offer(node.left); if (node.right != null) q.offer(node.right); } // add level order reverse for even if (odd) { result.add(level); } else { Collections.reverse(level); result.add(level); } // flip odd and even odd = !odd; } return result; } } ~~~ ### 源碼分析 區(qū)分奇數(shù)偶數(shù)行使用額外變量。 ### 復(fù)雜度分析 需要 reverse 的節(jié)點(diǎn)數(shù)目近似為 n/2, 故時(shí)間復(fù)雜度 O(n)O(n)O(n). 最下層節(jié)點(diǎn)數(shù)目最多 n/2, 故reverse 操作的空間復(fù)雜度可近似為 O(n/2)O(n/2)O(n/2). 總的時(shí)間復(fù)雜度為 O(n)O(n)O(n), 空間復(fù)雜度也為 O(n)O(n)O(n). ### Reference - [Binary Tree Zigzag Level Order Traversal 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/binary-tree-zigzag-level-order-traversal/) - [Printing a Binary Tree in Zig Zag Level-Order | LeetCode](http://articles.leetcode.com/2010/09/printing-binary-tree-in-zig-zag-level_18.html)