算法Day15 | 层序遍历，102，107，199，637，429，515，116，117，104，111，226，101网站首页 其他

算法Day15 | 层序遍历，102，107，199，637，429，515，116，117，104，111，226，101

雨后的放线君 2024-06-24 12:01:02

简介算法Day15 | 层序遍历，102，107，199，637，429，515，116，117，104，111，226，101

Day15

层序遍历

层序遍历就相当于图论中的广度优先搜索。
递归遍历就相当于图论中的深度优先搜索。
只使用二叉树结构，无法层序遍历。因为当你遍历到一个某个节点左节点时，无法遍历到其右节点。需要一个其他结构来辅助。选择使用队列queue保存每一层待遍历的元素。

102.二叉树的层序遍历

题目链接:102.二叉树的层序遍历
迭代

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;//记录每层节点
        vector<vector<int>> res;
        if (root) que.push(root);
        while (!que.empty()) {
            vector<int> res1;
            int size = que.size();//用于记录弹出节点个数，就是每层节点个数
            while (size--) {
                TreeNode* cur = que.front();
                que.pop();
                res1.push_back(cur->val);//记录节点数值
                if (cur->left) que.push(cur->left);//左节点入队列
                if (cur->right) que.push(cur->right);//右节点入队列
            }
            res.push_back(res1);
        }
        return res;
    }
};

递归

class Solution {
public:
    void recursive(TreeNode* cur, vector<vector<int>>& res, int depth) {
        if (!cur) return;//返回条件
        
        if (res.size() == depth) res.push_back(vector<int>());//开辟一个空的vector<int>
//        if (res.size() == depth) res.emplace_back();等价于上一行

        res[depth].push_back(cur->val);
        recursive(cur->left, res, depth + 1);
        recursive(cur->right, res, depth + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        int depth = 0;//给res二维数组，用来赋外层索引
        recursive(root, res, depth);
        return res;
    }
};

107.二叉树的层次遍历 II

题目链接:107.二叉树的层次遍历 II
因为节点遍历只能从根节点开始。所以就正常层序遍历，最后结果反转一下。
迭代

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> que;
        if (root) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> res1;
            while (size--) {
                TreeNode* cur = que.front();
                que.pop();
                res1.push_back(cur->val);
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            res.push_back(res1);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

递归

class Solution {
public:
    void recursion(TreeNode* root, vector<vector<int>>& res, int depth) {
        if (!root) return;

        if (res.size() == depth) res.emplace_back();
        res[depth].emplace_back(root->val);
        recursion(root->left, res, depth + 1);
        recursion(root->right, res, depth + 1);
    }
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        int depth = 0;
        recursion(root, res, depth);
        reverse(res.begin(), res.end());
        return res;
    }
};

199.二叉树的右视图

题目链接：199.二叉树的右视图
迭代

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        queue<TreeNode*> que;
        vector<int> res;
        if (root) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                TreeNode* cur = que.front();
                que.pop();
                if (!size)/*size = 0*/ res.push_back(cur->val);
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return res;
    }
};

递归

class Solution {
public:
    void recursion(TreeNode* root, vector<int>& res, int depth) {
        if (!root) return;
        if (res.size() == depth) res.emplace_back(root->val);
        
        //先加入右节点元素，因为是保存右节点
        recursion(root->right, res, depth + 1);
        recursion(root->left, res, depth + 1);
    }
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        int depth = 0;
        recursion(root, res, depth);
        return res;
    }
};

637.二叉树的层平均值

题目链接:637.二叉树的层平均值

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;
        queue<TreeNode*> que;
        if (root) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            double sum = 0;
            int cnt = 0;
            while (size--) {
                TreeNode* cur = que.front();
                que.pop();
                sum += cur->val;
                ++cnt;
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            res.push_back(sum / cnt);
        }
        return res;
    }
};

429.N叉树的层序遍历

题目链接:429.N叉树的层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        queue<Node*> que;
        vector<vector<int>> res;
        if (root) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            vector<int> res1;
            while (size--) {
                Node* cur = que.front();
                que.pop();
                res1.push_back(cur->val);
                for (auto& i : cur->children) {
                        que.push(i);
                }
            }
            res.push_back(res1);
        }
        return res;
    }
};

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

题目链接：515.在每个树行中找最大值

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;
        queue<TreeNode*> que;
        if (root) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            int maxValue = INT_MIN;
            while (size--) {
                TreeNode* cur = que.front();
                que.pop();
                maxValue = max(maxValue, cur->val);
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            res.push_back(maxValue);
        }
        return res;
    }
};

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

题目链接：116.填充每个节点的下一个右侧节点指针

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                Node* cur = que.front();
                que.pop();
                if (size) cur->next = que.front();//如果不是最后一个，与下一个节点相连
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return root;
    }
};

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

题目链接：117.填充每个节点的下一个右侧节点指针II
与上一道题一模一样

class Solution {
public:
    Node* connect(Node* root) {
        queue<Node*> que;
        if (root) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                Node* cur = que.front();
                que.pop();
                if (size) cur->next = que.front();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return root;
    }
};

104.二叉树的最大深度

题目链接：104.二叉树的最大深度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if (root) que.push(root);
        int res = 0;
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                TreeNode* cur = que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
            ++res;
        }
        return res;
    }
};

111.二叉树的最小深度

题目链接:111.二叉树的最小深度

class Solution {
public:
    int minDepth(TreeNode* root) {
        queue<TreeNode*> que;
        if (!root) return 0;
        if (root) que.push(root);
        int res = 1;//至少有一层
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                TreeNode* cur = que.front();
                que.pop();
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
                if (!cur->left && !cur->right) return res;
            }
            ++res;
        }
        return res;
    }
};

226.翻转二叉树

题目链接：226.翻转二叉树
前、后序遍历很简单。
前序递归

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        swap(root->left, root->right);//中
        invertTree(root->left);//左
        invertTree(root->right);//右
        return root;
    }
};

后序递归

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        invertTree(root->left);//左
        invertTree(root->right);//右
        swap(root->left, root->right);//中
        return root;
    }
};

中序递归：代码上看是两次root->left

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        invertTree(root->left);//左
        swap(root->left, root->right);//中
        //因为上一行代码已经处理过左树，处理完换成右树
        //接下来要处理的是原来的右树，但是已经变成左树了
        invertTree(root->left);//右
        return root;
    }
};

前序迭代

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root) st.push(root);
        while (!st.empty()) {
            TreeNode* cur = st.top();
            if (cur) {
                st.pop();
                if (cur->right) st.push(cur->right);//右
                if (cur->left) st.push(cur->left);//左
                st.push(cur);//中
                st.push(nullptr);
            } else {
                st.pop();
                cur = st.top();
                st.pop();
                swap(cur->left, cur->right);
            }
        }
        return root;
    }
};

中序迭代

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        stack<TreeNode*> st;
        if (root) st.push(root);
        while (!st.empty()) {
            TreeNode* cur = st.top();
            st.pop();
            if (cur) {
                if (cur->right) st.push(cur->right);//右
                st.push(cur);//中
                st.push(nullptr);
                if (cur->left) st.push(cur->left);//左
            } else {
                cur = st.top();
                st.pop();
                swap(cur->left, cur->right);
            }
        }
        return root;
    }
};

后序迭代

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

层序迭代

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        queue<TreeNode*> que;
        if (root) que.push(root);
        while (!que.empty()) {
            int size = que.size();
            while (size--) {
                TreeNode* cur = que.front();
                que.pop();
                swap(cur->left, cur->right);
                if (cur->left) que.push(cur->left);
                if (cur->right) que.push(cur->right);
            }
        }
        return root;
    }
};

101.对称二叉树

题目链接：101.对称二叉树
因为是先判断左右是否对称，再将结果传给中。顺序为左右中。所以是后序遍历。
递归

class Solution {
public:
    bool recursion(TreeNode* cur1, TreeNode* cur2) {
        //先排除空节点
        //这两个语句不能调换
        if (!cur1 && !cur2) return true;
        //非空之后，再排除值。
        if (!cur1 || !cur2 || cur1->val != cur2->val/*值判断一定要在非空之后*/) return false;
        
        auto outside = recursion(cur1->left, cur2->right);
        auto inside = recursion(cur1->right, cur2->left);
        return outside && inside;
    }
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        return recursion(root->left, root->right);
    }
};

对于判断条件需要强调：

if (!cur1 && !cur2) return true;
if (!cur1 || !cur2) return false;

第一个if判断了同时为空的条件，满足条件，执行return。如果执行到第二条if语句，表示第一个if一定失效，即cur1和cur2不可能同时为空（有cur1为空，则cur2不为空；cur1不为空，则cur2为空），所以第二个if只需要判断cur1不为空（cur2一定为空）或者cur2不为空（cur1一定为空）即可。重要的是这两条if不能颠倒顺序。

if (!cur1 && !cur2) return true;
if (!cur1 && cur2) return false;
if (cur1 && !cur2) return false;

也就是，上面三条if可以用两条if来代替。因为第二条的if中的cur2和第三条if中的cur1一定是非空的，是多余的。

由于if后是return语句，所以可以写先if( && )再写if( || )。更具一般性地，if( && ) else if ( || )。

迭代

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if (!root) return true;
        stack<TreeNode*> st;
        st.push(root->left);
        st.push(root->right);
        while (!st.empty()) {
            auto leftNode = st.top();st.pop();
            auto rightNode = st.top();st.pop();
            if (!leftNode && !rightNode) continue;
            if (!leftNode || !rightNode || leftNode->val != rightNode->val)
                return false;
            st.push(leftNode->left);
            st.push(rightNode->right);
            st.push(leftNode->right);
            st.push(rightNode->left);
        }
        return true;
    }
};