Traverse

102 Level Traverse - top down

• BFS, use queue

• Queue size is changing in for loop

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    Deque<TreeNode> queue = new LinkedList<>();

    if (root == null){
        return result;
    }
    queue.add(root);
    while(!queue.isEmpty()){
        List<Integer> level = new ArrayList<>();
        // queue size is changing is for loop
        int level_size = queue.size();  
        for (int i = 0; i < level_size; i++){
            TreeNode node = queue.poll();
            level.add(node.val);

            if (node.left != null){
                queue.add(node.left);
            }
            if (node.right != null){
                queue.add(node.right);
            }
        }
        result.add(level);
    }
    return result;
}

107 Level traverse - bottom up

1. top down then reverse

2. get the depth first, use dfs to store elements in each level

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null){
        return result;
    }
    int maxLevel = depth(root);
    int curLevel = 1;
    while(curLevel <= maxLevel){
        List<Integer> level = new ArrayList<>();
        dfs(root, curLevel, maxLevel, level);
        result.add(level);
        maxLevel--;
    }
    return result;
}

private int depth(TreeNode root){
    if (root == null){
        return 0;
    }
    int left = depth(root.left);
    int right = depth(root.right);
    return 1 + (left > right ? left : right);
}

private void dfs(TreeNode root, int curLevel, int maxLevel, List<Integer> level){
    if (root == null){
        return ;
    }
    if (curLevel == maxLevel){
        level.add(root.val);
    }
        dfs(root.left, curLevel + 1, maxLevel, level);
        dfs(root.right, curLevel + 1, maxLevel, level);
    }

103 ZigZag

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).

• Add array to result

• Use % to decide odd or even array

• ArrayList.add(0, int) - addFirst

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null){
        return result;
    }
    preorder(root, 0, result);
    return result;
}

private void preorder(TreeNode root, int level, List<List<Integer>> result){
    if (root == null){
        return;
    }
    if (result.size() < level + 1){
        result.add(new ArrayList<>());
    }
    List<Integer> tmp = result.get(level);
    if (level % 2 == 0){
        tmp.add(root.val);
    }else{
        tmp.add(0, root.val); // addFirst
    }
    preorder(root.left, level + 1, result);
    preorder(root.right, level + 1, result);
}

297. Serialize and Deserialize Binary Tree

• output string is preorder string

def serialize(self, root):
    s = ''
    if root is None: s += '#' + ','
    else: 
        s += str(root.val) + ','
        s += self.serialize(root.left)
        s += self.serialize(root.right)   
    return s


def deserialize(self, data):
    q = data.split(',')
    return self.dHelper(q)


def dHelper(self, q):
    val = q.pop(0)
    if val == '#': return None
    else:
        node = TreeNode(val)
        node.left = self.dHelper(q)
        node.right = self.dHelper(q)
        
    return node