[leetcode] Binary Tree Zigzag Level Order Traversal | zigzag形状traverse树

Posted by: lexigrey on: October 19, 2013

• In: leetcode
• Leave a Comment

树的dfs变形，还是两个list来回倒。但是这题上来就写还不行，真心得在纸上画一画才能看出来规律。一开始觉得keep一个boolean，正常顺序就加后面，逆序就加前面呗，但是没注意到parent其实很可能已经不是原来顺序的了。画个四层的树就能看出来咋回事了。还有一个小bug就是最开始的boolean reverse应该是true，因为他代表了“parent下面一层要什么顺序”，而不是parent本身是什么顺序。所以还是，变量的物理意义一定要搞清再写！

public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    if (root == null)
        return result;
    ArrayList<TreeNode> parents = new ArrayList<TreeNode>();
    boolean reverse = true;//first children line is reversed
    parents.add(root);
    while (!parents.isEmpty()) {
        ArrayList<TreeNode> children = new ArrayList<TreeNode>();
        for (int i = parents.size() - 1; i >= 0; i--) {
            TreeNode parent = parents.get(i);
            if (!reverse) {// the children list wants to be normal order
                if (parent.left != null)
                    children.add(parent.left);
                if (parent.right != null)
                    children.add(parent.right);
            } else { //the children wants to be right to left
                if (parent.right != null)
                    children.add(parent.right);
                if (parent.left != null)
                    children.add(parent.left);
            }
        }
        result.add(convertToIntegerList(parents));
        reverse = !reverse;
        parents = children;
    }
    return result;
}

Tags: bfs, tree