今天的題單：

• Move Zeroes

• Symmetric Tree

283. Move Zeroes

把陣列中所有的 0 都移到陣列後方。

思路：用 two pointer 紀錄原本陣列的開始 (front) 和結尾處 (end)，移動 front pointer ，當遇到 0 的時候就把 front 到 end 中間整段元素往前移一格，並在結尾處補 0。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        vector<int>::iterator front = nums.begin();
        vector<int>::iterator end = nums.end();

        while (next(front) != end) {
            if (*front == 0) {
                copy(next(front), end, front);
                *(prev(end)) = 0;
                end--;
            } else {
                front++;
            }
        }
    }
};

101. Symmetric Tree

判斷一顆 binary tree 是不是對稱的。

思路: 一層一層比較，同一層需要左右反過來比較。

實作一：iterative 方法，利用 BFS，從上往下一層一層做

/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        // bfs
        queue<TreeNode*> q_left;
        queue<TreeNode*> q_right;

        q_left.push(root->left);
        q_right.push(root->right);

        while (!q_left.empty() && !q_right.empty()) {
            // compare
            TreeNode* l = q_left.front();
            TreeNode* r = q_right.front();
            if (l == nullptr ^ r == nullptr) {
                return false;
            } else {
                if (l != nullptr && r != nullptr) {
                    if (l->val != r->val) {
                        return false;
                    } else {
                        q_left.push(l->left);
                        q_left.push(l->right);
                        q_right.push(r->right);
                        q_right.push(r->left);
                    }
                } 
                q_left.pop();
                q_right.pop();
            }
        }

        return q_left.empty() && q_right.empty();
    }
};

實作二﹔recursive 方法，利用 DFS 同時走左右兩邊的子樹，走對稱的方向

/**
 * 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:
    bool isSymmetric(TreeNode* root) {  
        return mirror(root->left, root->right);
    }

    bool mirror(TreeNode* left, TreeNode* right) {
        if (left == nullptr ^ right == nullptr) {
            return false;
        }
        if (left == nullptr && right == nullptr) {
            return true;
        }
        
        if (left->val == right->val) {
            return mirror(left->left, right->right) && mirror(left->right, right->left);
        } else {
            return false;
        }
    }
};

一些感想

在寫 tree traversal 的時候有時會遇到需要判斷兩個 pointer 是不是 nullptr。
我原本都會寫成﹔

if (p1 == nullptr ^ p2 == nullptr) { // one of them is nullptr
  // do something
}
if (p1 == nullptr && p2 == nullptr) { // p1 and p2 are nullptr
  // do something
}
// both p1 and p2 are not nullptr 
// do something 

在 sample code 上比較常看到另一種寫法﹔

if (p1 == nullptr && p2 == nullptr) { // p1 and p2 are nullptr
  // do something
}
if (p1 == nullptr || p2 == nullptr) { // one of them is nullptr
  // do something
}
// both p1 and p2 are not nullptr 
// do something

兩種方法一樣是把兩個 pointer 的關係分成三個一樣情況，差在判斷順序不一樣，也許在不同場合會有不同用處。