当前位置:首页 » JAVA技术教程

leetcode-103.+Binary+Tree+Zigzag+Level+Order+Traversal

2016-12-27 09:48 本站整理 浏览(4)

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]

]

和上一题层序遍历很类似,不过要求是Z字型遍历,所以这里用栈,而且需要一个bollean变量来表示方向。

[code]/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        Stack<TreeNode> tmp = new Stack<TreeNode>();
        if(root!=null) tmp.add(root);
        boolean flag = true;
        while(tmp.size()!=0){
            List<Integer> ad = new ArrayList<Integer>();
            Stack<TreeNode> replace = new Stack<TreeNode>();
            while(tmp.size()!=0){
                TreeNode node = tmp.pop();
                if(!flag){
                    if(node.right!=null)replace.add(node.right);
                    if(node.left!=null)replace.add(node.left);
                    ad.add(node.val);
                }else{
                    if(node.left!=null)replace.add(node.left);
                    if(node.right!=null)replace.add(node.right);
                    ad.add(node.val);
                }
            }
            flag = !flag;
            tmp = replace;
            ret.add(ad);
        }
        return ret;
    }
}