算法训练day15 层序遍历、LeetCode 226.101

层序遍历

层序遍历是一种广度优先的遍历方式

队列符合广度优先层层深入的逻辑，栈符合深度优先（递归）的逻辑

//逐层完整遍历
class Solution
{
public:
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        queue<TreeNode *> que;
        if (root != NULL)
            que.push(root);
        vector<vector<int>> result;
        while (!que.empty())
        {
            int size = que.size();
            vector<int> vec;
            for (int i = 0; i < size; i++)
            {
                TreeNode *node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left)
                    que.push(node->left);
                if (node->right)
                    que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

//递归法（单支深入）
//depth标记层深
class Solution
{
    void order(TreeNode *cur, vector<vector<int>> &result, int depth)
    {
        if (cur == nullptr)
            return;
        if (result.size() == depth)
            result.push_back(vector<int>());
        result[depth].push_back(cur->val);
        order(cur->left, result, depth + 1);
        order(cur->right, result, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode *root)
    {
        vector<vector<int>> result;
        int depth=0;
        order(root,result,depth);
        return result;
    }
};

226.翻转二叉树

题目

226. 翻转二叉树 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

想法是使用递归

重复过程是将根节点的两个子节点交换
结束条件是根节点没有子节点

class Solution
{
public:
    TreeNode *invertTree(TreeNode *root)
    {
        if (root == nullptr)
            return root;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

101. 对称二叉树

题目

101. 对称二叉树 - 力扣（LeetCode）

题解

代码随想录 (programmercarl.com)

比较根节点左右子树是否对称

采取不同顺序的后序遍历左右中 | 右左中

class Solution {
public:
    bool compare(TreeNode* left, TreeNode* right) {
        if (left == NULL && right != NULL) return false;
        else if (left != NULL && right == NULL) return false;
        else if (left == NULL && right == NULL) return true;
        else if (left->val != right->val) return false;
        else return compare(left->left, right->right) && compare(left->right, right->left);

    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return true;
        return compare(root->left, root->right);
    }
};