103. Binary Tree Zigzag Level Order Traversal (M)

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).
 
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []
 
Constraints:
The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100

A:
这道题面试的时候，要说。 有2种思路。  dfs 或者bfs
如果bfs的话，就是每层打印。 那么有2种方法，   递归  或者 迭代。


---------------------3rd pass-------- DFS ---------------

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> all = new ArrayList<List<Integer>>();
        int height = getHeight(root);
        for(int i =0;i<height;i++){
            all.add(new ArrayList<Integer>());
        }
        dfs(all,root,0);
        return all;
    }
    private void dfs(List<List<Integer>> all, TreeNode root, int level){
        if(root == null)
            return;
        if(level %2==0){
            all.get(level).add(root.val);
        }else{
            all.get(level).add(0,root.val);
        }
            dfs(all,root.left,level+1);
            dfs(all,root.right,level+1);
    }
    private int getHeight(TreeNode root){
        if(root == null)
            return 0;
        else
            return 1+Math.max(getHeight(root.left),getHeight(root.right));
    }
}

--------------------------1 st pass-----------------------
就是把 “Binary Tree Level Order Traversal ” 问题里的一句
普通的 level order traversal，只不过每层的时候，按照flag，加入结果的位置不同 而已

/**

* Definition for a binary tree node.

* struct TreeNode {

* int val;

* TreeNode *left;

* TreeNode *right;

* TreeNode() : val(0), left(nullptr), right(nullptr) {}

* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),

* right(right) {}

* };

*/

class Solution {

public:

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {

bool l2r = true;

vector<vector<int>> res;

stack<TreeNode*> S;

if (root)

S.push(root);

while (!S.empty()) {

stack<TreeNode*> newS;

vector<int> curLine;

while (!S.empty()) {

auto tmp = S.top();

S.pop();

curLine.push_back(tmp->val);

if (l2r) {

if (tmp->left)

newS.push(tmp->left);

if (tmp->right)

newS.push(tmp->right);

} else {

if (tmp->right)

newS.push(tmp->right);

if (tmp->left)

newS.push(tmp->left);

}

}

l2r = !l2r;

S = newS;

res.push_back(curLine);

}

return res;

}

};

Mistakes: