[leetcode] Binary Tree Zigzag Level Order Traversal | zigzag形状traverse树
Posted October 19, 2013
on:树的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;
}
Leave a Reply