[数据结构与算法]代码随想录算法训练营第十五天|102. 二叉树的层序遍历、226. 翻转二叉树、101. 对称二叉树

LeetCode?102. 二叉树的层序遍历

链接：102. 二叉树的层序遍历

思路：

层序遍历为从左到右，从上到下依次遍历二叉树的节点，可以采用BFS（广度优先搜索）的方式。实现BFS算法需要使用队列这一数据结构。首先把根节点压入队列，每经过一层，会弹出当前层的节点，并把下一层的所有子节点压入队列，所以在到达下一层的时候，队列的大小会始终等于这一层的节点数。用一个循环把该层的所有节点都push进一个数组，并在循环结束的时候把该数组push到另一个由数组组成的数组里，即可得到二叉树的层序遍历。

代码：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> myQueue;
        vector<vector<int>> ans;
        if (root == nullptr)
            return ans;
        myQueue.push(root);
        while (!myQueue.empty())
        {
            // 获取每一层的节点个数
            int size = myQueue.size();
            // 把每一层的节点都放进数组
            vector<int> tmp;
            for (int i = 0; i < size; i++)
            {
                TreeNode *node = myQueue.front();
                myQueue.pop();
                if (node->left)
                    myQueue.push(node->left);
                if (node->right)
                    myQueue.push(node->right);
                tmp.push_back(node->val);

            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

时间复杂度：O(n)

空间复杂度：O(n)

使用层序遍历可以一下子解决很多相似的问题，只需要稍微改几行代码即可。

LeetCode?107. 二叉树的层序遍历 II

107. 二叉树的层序遍历 II

完全一样的代码，只不过是自底向上的，所以只需要在遍历结束后反转一下数组即可

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> ans;
        if (root == nullptr)
            return ans;
        queue<TreeNode*> myQueue;
        myQueue.push(root);
        while (!myQueue.empty())
        {
            int size = myQueue.size();
            vector<int> tmp;
            for (int i = 0; i < size; i++)
            {
                TreeNode *node = myQueue.front();
                myQueue.pop();
                if (node->left)
                    myQueue.push(node->left);
                if (node->right)
                    myQueue.push(node->right);
                tmp.push_back(node->val);
            }
            ans.push_back(tmp);
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

LeetCode?199. 二叉树的右视图

199. 二叉树的右视图

只需要在遍历每层的时候把最后一个元素压入数组即可

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> myQueue;
        vector<int> ans;
        if (root == nullptr)
            return ans;
        myQueue.push(root);
        while (!myQueue.empty())
        {
            int size = myQueue.size();

            for (int i = 0; i < size; i++)
            {
                TreeNode *node = myQueue.front();
                myQueue.pop();
                if (node->left)
                    myQueue.push(node->left);
                if (node->right)
                    myQueue.push(node->right);
                // 把每层最右边的元素放入数组
                if (i == size - 1)
                    ans.push_back(node->val);
            }
        }
        return ans;
    }
};

LeetCode?637. 二叉树的层平均值

637. 二叉树的层平均值

遍历每层的时候计算该层节点值的和，然后压入数组时求一下平均数即可

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        queue<TreeNode*> myQueue;
        vector<double> ans;
        if (root == nullptr)
            return ans;
        myQueue.push(root);
        while (!myQueue.empty())
        {
            // 获取每一层的节点个数
            int size = myQueue.size();
            double sum = 0;
            for (int i = 0; i < size; i++)
            {
                TreeNode *node = myQueue.front();
                myQueue.pop();
                if (node->left)
                    myQueue.push(node->left);
                if (node->right)
                    myQueue.push(node->right);
                sum += node->val;

            }
            ans.push_back((double)sum / size);
        }
        return ans;
    }
};

LeetCode 429.N叉树的层序遍历

429. N 叉树的层序遍历

唯一的区别是压入队列的时候用的是一个数组

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> myQueue;
        vector<vector<int>> ans;
        if (root == nullptr)
            return ans;
        myQueue.push(root);
        while (!myQueue.empty())
        {
            // 获取每一层的节点个数
            int size = myQueue.size();
            // 把每一层的节点都放进数组
            vector<int> tmp;
            for (int i = 0; i < size; i++)
            {
                Node *node = myQueue.front();
                myQueue.pop();
                for (Node* node : node->children)
                {
                    if (node)
                        myQueue.push(node);
                }
                tmp.push_back(node->val);

            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

LeetCode?515. 在每个树行中找最大值

515. 在每个树行中找最大值

更简单，记录一下最大值就可以了，唯一要注意的是int的精度问题

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        queue<TreeNode*> myQueue;
        vector<int> ans;
        if (root == nullptr)
            return ans;
        myQueue.push(root);
        while (!myQueue.empty())
        {
            // 获取每一层的节点个数
            int size = myQueue.size();
            int max = INT_MIN;
            for (int i = 0; i < size; i++)
            {
                TreeNode *node = myQueue.front();
                myQueue.pop();
                if (node->left)
                    myQueue.push(node->left);
                if (node->right)
                    myQueue.push(node->right);
                if (max < node->val)
                    max = node->val;
            }
            ans.push_back(max);
        }
        return ans;
    }
};

LeetCode?116. 填充每个节点的下一个右侧节点指针

116. 填充每个节点的下一个右侧节点指针

在每层把前size-1个节点加入next指针

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> myQueue;
        if (root == nullptr)
            return root;
        myQueue.push(root);
        while (!myQueue.empty())
        {
            // 获取每一层的节点个数
            int size = myQueue.size();
            for (int i = 0; i < size; i++)
            {
                Node *node = myQueue.front();
                myQueue.pop();
                // 给前size-1个节点加入next指针
                if (i < size - 1)
                    node->next = myQueue.front();

                if (node->left)
                    myQueue.push(node->left);
                if (node->right)
                    myQueue.push(node->right);
            }
        }
        return root; 
    }
};

LeetCode?117. 填充每个节点的下一个右侧节点指针 II

117. 填充每个节点的下一个右侧节点指针 II

同上代码无任何区别

LeetCode?104. 二叉树的最大深度

104. 二叉树的最大深度

每经过一层就depth++最后返回depth即可

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> myQueue;
        if (root == nullptr)
            return 0;
        myQueue.push(root);
        int depth = 0;
        while (!myQueue.empty())
        {
            // 获取每一层的节点个数
            int size = myQueue.size();
            for (int i = 0; i < size; i++)
            {
                TreeNode *node = myQueue.front();
                myQueue.pop();
                if (node->left)
                    myQueue.push(node->left);
                if (node->right)
                    myQueue.push(node->right);
            }
            depth++;
        }
        return depth;
    }
};

LeetCode?111. 二叉树的最小深度

111. 二叉树的最小深度

稍微有点不同的是增加一个判断node->left和node->right的条件，如果两个指针都为空则直接返回depth

class Solution {
public:
    int minDepth(TreeNode* root) {
        queue<TreeNode*> myQueue;
        if (root == nullptr)
            return 0;
        myQueue.push(root);
        int depth = 0;
        while (!myQueue.empty())
        {
            // 获取每一层的节点个数
            int size = myQueue.size();
            depth++;
            for (int i = 0; i < size; i++)
            {
                TreeNode *node = myQueue.front();
                myQueue.pop();
                if (node->left)
                    myQueue.push(node->left);
                if (node->right)
                    myQueue.push(node->right);
                 // 当左右孩子都为空的时候，说明是最低点的一层了，退出
                if (!node->left && !node->right)
                    return depth;
            }
        }
        return depth;
    }
};

LeetCode?226. 翻转二叉树

链接：226. 翻转二叉树

递归法：

思路：

用前序遍历或者后续遍历的方式，反转left和right两个节点的指针即可。

代码：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr)
            return root;
        dfs(root);
        return root;
    }
    void dfs(TreeNode *root)
    {
        if (!root)
            return;
        TreeNode * temp = root->left;
        root->left = root->right;
        root->right = temp;
        dfs(root->left);
        dfs(root->right);
    }
};

迭代法：

思路：

按照迭代法写前序遍历的思路，需要操作的时候交换两个指针即可。

代码：

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr)
            return root;
        stack<TreeNode*> myStack;
        myStack.push(root);
        while (!myStack.empty())
        {
            TreeNode* node = myStack.top();
            myStack.pop();
            if (node->right)
                myStack.push(node->right);
            if (node->left)
                myStack.push(node->left);
            swap(node->left, node->right);
        }
        return root;
    }
};

LeetCode?101. 对称二叉树

链接：101. 对称二叉树

递归法：

思路：

该题同样用了递归法和迭代法两种思路，不过大体思路还是一致的。判断一个二叉树是否对称，实际上就是判断根节点下的两个子树是否是对称的。左子树和右子树同时用后续遍历，只不过左子树遍历方式为左右中，右子树的遍历方式改为右左中，这样两个子树遍历的节点正好是对称的，只要每次对比两个节点是否一样即可。

对比两个节点是否一样需要考虑多种情况。首先要判断两个节点是否为空，如果其中一个为空另一个不为空，则返回false。如果两个都为空，则返回true。如果两个都不为空，则比较两个节点的值是否一致，如不一致则返回false。最后要考虑两个节点的值一致的情况，在左右节点一致时递归调用函数检查它们的子节点是否也是对称的。

代码：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return dfs(root->left, root->right);
    }
    bool dfs(TreeNode* leftNode, TreeNode* rightNode)
    {
        if (leftNode == nullptr && rightNode != nullptr) return false;
        else if (leftNode != nullptr && rightNode == nullptr) return false;
        else if (leftNode == nullptr && rightNode == nullptr) return true;
        else if (leftNode->val != rightNode->val) return false;
        if (dfs(leftNode->left, rightNode->right) && dfs(leftNode->right, rightNode->left))
            return true;
        else
            return false;
    }
};

迭代法：

思路：

迭代法采用了层序遍历，但和层序遍历并不完全相同，而是在每一层同时pop左子树和右子树两个节点，并判断这两个节点是否相同。判断条件和递归法的方式基本相同，不同点则是在两个节点相同的时候，在这里需要同时把左节点的两个子节点和右节点的两个子节点按配对放入队列，左子树的左节点对应右子树的右节点，反之也是一样的，这样在下次同时pop出来的两个左右子节点也是对应的。

代码：

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        queue<TreeNode*> myQueue;
        myQueue.push(root->left);
        myQueue.push(root->right);
        while (!myQueue.empty())
        {
            TreeNode *left = myQueue.front();myQueue.pop();
            TreeNode *right = myQueue.front();myQueue.pop();
            if (left != nullptr && right == nullptr)
                return false;
            else if (left == nullptr && right != nullptr)
                return false;
            else if (left != nullptr && right != nullptr && left->val != right->val)
                return false;
            else if (left != nullptr && right != nullptr && left->val == right->val)
            {
                myQueue.push(left->left);
                myQueue.push(right->right);
                myQueue.push(left->right);
                myQueue.push(right->left);
            }
        }
        return true;
    }
};