LeetCode-103

题目

结果

代码

终稿

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return new LinkedList<>();
        }

        List<List<Integer>> ans = new LinkedList<>();
        List<TreeNode> treeNodes = new ArrayList<>();
        treeNodes.add(root);
        boolean direction = false;

        while (!treeNodes.isEmpty()) {
            List<Integer> integers = new LinkedList<>();
            // Left to right
            if (!direction) {
                for (TreeNode node : treeNodes) {
                    integers.add(node.val);
                }
            } else { // Right to left
                for (int i = treeNodes.size() - 1; i >= 0; i--) {
                    integers.add(treeNodes.get(i).val);
                }
            }
            ans.add(integers);

            // Next level
            List<TreeNode> tmp = new LinkedList<>(treeNodes);
            treeNodes.clear();
            for (TreeNode node : tmp) {
                if (node.left != null) {
                    treeNodes.add(node.left);
                }
                if (node.right != null) {
                    treeNodes.add(node.right);
                }
            }
            direction = !direction;
        }
        return ans;
    }
}

初稿

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if (root == null) {
            return new LinkedList<>();
        }
        List<List<Integer>> ans = new LinkedList<>();
        ans.add(List.of(root.val));
        boolean direction = false;
        Deque<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        while (!deque.isEmpty()) {
            List<TreeNode> row = new ArrayList<>(deque);
            deque.clear();
            for (TreeNode node : row) {
                if (node.left != null) {
                    deque.add(node.left);
                }
                if (node.right != null) {
                    deque.add(node.right);
                }
            }
            List<Integer> currLevel = new LinkedList<>();
            // Left to right
            if (direction) {
                for (TreeNode node : row) {
                    if (node.left != null) {
                        currLevel.add(node.left.val);
                    }
                    if (node.right != null) {
                        currLevel.add(node.right.val);
                    }
                }
            } else { // Right to left
                for (int i = row.size() - 1; i >= 0; i--) {
                    TreeNode node = row.get(i);
                    if (node.right != null) {
                        currLevel.add(node.right.val);
                    }
                    if (node.left != null) {
                        currLevel.add(node.left.val);
                    }
                }
            }
            if (!currLevel.isEmpty()) {
                ans.add(currLevel);
            }
            direction = !direction;
        }
        return ans;
    }
}

Golang

func zigzagLevelOrder(root *TreeNode) (ans [][]int) {
	if root == nil {
		return
	}
	var queue []*TreeNode
	queue = append(queue, root)

	var direction bool
	for len(queue) != 0 {
		var level []int
		var tmp []*TreeNode
		for _, node := range queue {
			level = append(level, node.Val)
			if node.Left != nil {
				tmp = append(tmp, node.Left)
			}
			if node.Right != nil {
				tmp = append(tmp, node.Right)
			}
		}
		if direction {
			ans = append(ans, level)
		} else {
			ans = append(ans, rvs(level))
		}
		queue = tmp
		direction = !direction
	}

	return
}

func rvs(nums []int) (ans []int) {
	for i := len(nums) - 1; i >= 0; i-- {
		ans = append(ans, nums[i])
	}
	return
}

复杂度

时间复杂度：O（N）

空间复杂度：O（N）

疑惑

初稿通过之后，感觉代码写的不美观，我稍加调整了一下，算法明明是一样的，但是速度反而慢了1ms，我认为这是误差，但重复试了很多遍之后，就是有这1ms的差距，怪事。