leetcode_day15

今日内容：

- 102.层序遍历 - 226.翻转二叉树 - 101.对称二叉树

层序遍历

思路就是用队列记录逐层，这样顺序不会变。进入一层时最好记录队列初长度，然后根据长度遍历该层，避免根据队列是否空而判断该层是否遍历结束，便于即时将子节点入队

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> ans;
    vector<int> temp;
    if(root == nullptr) return {};
    TreeNode * cur = root;
    queue<TreeNode*> q;
    q.push(cur);
    while(!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            cur = q.front();
            q.pop();
            temp.push_back(cur->val);
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
        ans.push_back(temp);
        temp.clear();
    }
    return ans;
}

翻转二叉树

递归版比较简单，太过简单，所以skip

迭代版就看作在遍历，而且是前序遍历那种单循环，出栈后把左右节点交换，然后压栈左右节点继续就行，给出循环部分的核心代码本来就是核心代码模式，又再核心……

while(!st.empty()) {
    TreeNode* node = st.top();              // 中
    st.pop();
    swap(node->left, node->right);
    if(node->right) st.push(node->right);   // 右
    if(node->left) st.push(node->left);     // 左
}

对称二叉树

递归版很简单，写一个辅助函数判断左右节点是不是相等，是树就接着递归，然后从根开始对每一个分支节点的左右孩子判断就行 代码没写，偷了个懒😜

迭代版要难一点，仅限于手写层面，思路不难

迭代需要用队列或者栈等来存，但是不是按左右顺序挨个入队，而是左右对应交替入队，这样方便判断是否相等

下附carl的漂亮含注释代码，carl原文链接

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        queue<TreeNode*> que;
        que.push(root->left);   // 将左子树头结点加入队列
        que.push(root->right);  // 将右子树头结点加入队列
        
        while (!que.empty()) {  // 接下来就要判断这两个树是否相互翻转
            TreeNode* leftNode = que.front(); que.pop();
            TreeNode* rightNode = que.front(); que.pop();
            if (!leftNode && !rightNode) {  // 左节点为空、右节点为空，此时说明是对称的
                continue;
            }

            // 左右一个节点不为空，或者都不为空但数值不相同，返回false
            if ((!leftNode || !rightNode || (leftNode->val != rightNode->val))) {
                return false;
            }
            que.push(leftNode->left);   // 加入左节点左孩子
            que.push(rightNode->right); // 加入右节点右孩子
            que.push(leftNode->right);  // 加入左节点右孩子
            que.push(rightNode->left);  // 加入右节点左孩子
        }
        return true;
    }
};