【代码随想录】day13

day13 二叉树1

二叉树定义

链式存储的二叉树节点的定义方式：

struct TreeNode{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x): val(x), left(nullptr), right(nullptr) {}
};

144.二叉树的前序遍历

方法一、递归法：

class Solution {
public:
    void traversal(vector<int> &res, TreeNode *node) {
        if (node == nullptr) {
            return;
        }
        res.push_back(node->val);
        traversal(res, node->left);
        traversal(res, node->right);
    }

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(res, root);
        return res;
    }
};

方法二、迭代法：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> st;
        if (root == nullptr) {
            return res;
        }
        st.push(root);
        while (!st.empty()) {
            int n = st.size();
            while (n --) {
                TreeNode *node = st.top();
                st.pop();
                res.push_back(node->val);
                if (node->right) {
                    st.push(node->right);
                }
                if (node->left) {
                    st.push(node->left);
                }
            }
        }
        return res;
    }
};

145.二叉树的后序遍历

递归法：

class Solution {
public:
    void traversal(vector<int> &res, TreeNode *node) {
        if (node == nullptr) {
            return;
        }
        traversal(res, node->left);
        traversal(res, node->right);
        res.push_back(node->val);
    }

    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(res, root);
        return res;
    }
};

迭代法：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {
            int n = st.size();
            while (n --) {
                TreeNode *node = st.top();
                st.pop();
                res.push_back(node->val);
                if (node->left) {
                    st.push(node->left);
                }
                if (node->right) {
                    st.push(node->right);
                }
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

94.二叉树的中序遍历

递归法：

class Solution {
public:
    void traversal(vector<int> &res, TreeNode *node) {
        if (node == nullptr) {
            return;
        }
        traversal(res, node->left);
        res.push_back(node->val);
        traversal(res, node->right);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        traversal(res, root);
        return res;
    }
};

迭代法：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        stack<TreeNode*> st;
        TreeNode *cur = root;
        while (cur != nullptr || !st.empty()) {
            if (cur != nullptr) {
                st.push(cur);
                cur = cur->left;
            }
            else {
                cur = st.top();
                st.pop();
                res.push_back(cur->val);
                cur = cur->right;
            }
        }
        return res;
    }
};

102.二叉树的层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if (root == nullptr) {
            return res;
        }
        deque<TreeNode*> q;
        q.push_back(root);
        while (!q.empty()) {
            vector<int> temp;
            int n = q.size();
            while (n --) {
                TreeNode *node = q.front();
                q.pop_front();
                temp.push_back(node->val);
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
            res.push_back(temp);
        }
        return res;
    }
};

107.二叉树的层次遍历II

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
        if (root == nullptr) {
            return res;
        }
        deque<TreeNode*> q;
        q.push_back(root);
        while (!q.empty()) {
            int n = q.size();
            vector<int> temp;
            while (n --) {
                TreeNode *node = q.front();
                q.pop_front();
                temp.push_back(node->val);
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
            res.push_back(temp);
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

199.二叉树的右视图

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        deque<TreeNode*> q;
        q.push_back(root);
        while (!q.empty()) {
            int n = q.size() - 1;
            while (n --) {
                TreeNode *node = q.front();
                q.pop_front();
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
            TreeNode *addNode = q.front();
            q.pop_front();
            res.push_back(addNode->val);
            if (addNode->left) {
                q.push_back(addNode->left);
            }
            if (addNode->right) {
                q.push_back(addNode->right);
            }
        }
        return res;
    }
};

637.二叉树的层平均值

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;
        deque<TreeNode*> q;
        q.push_back(root);
        while (!q.empty()) {
            double num = 0;
            int n = q.size();
            for (int i = 0; i < n; i ++) {
                TreeNode *node = q.front();
                q.pop_front();
                num += node->val;
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
            res.push_back(num / n);
        }
        return res;
    }
};

429.N叉树的层序遍历

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> res;
        if (root == nullptr) {
            return res;
        }
        deque<Node*> q;
        q.push_back(root);
        while (!q.empty()) {
            int n = q.size();
            vector<int> temp;
            while (n --) {
                Node *node = q.front();
                q.pop_front();
                temp.push_back(node->val);
                vector<Node*> ch = node->children;
                for (int i = 0; i < ch.size(); i ++) {
                    q.push_back(ch[i]);
                }
            }
            res.push_back(temp);
        }
        return res;
    }
};

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

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> res;
        if (root == nullptr) {
            return res;
        }
        deque<TreeNode*> q;
        q.push_back(root);
        while (!q.empty()) {
            int max_num = INT_MIN;
            int n = q.size();
            while (n --) {
                TreeNode *node = q.front();
                q.pop_front();
                max_num = node->val > max_num ? node->val : max_num;
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
            res.push_back(max_num);
        }
        return res;
    }
};

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

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) {
            return root;
        }
        deque<Node*> q;
        if (root->left) {
            q.push_back(root->left);
        }
        if (root->right) {
            q.push_back(root->right);
        }
        while (!q.empty()) {
            int n = q.size();
            while (n --) {
                Node* node = q.front();
                q.pop_front();
                if (n > 0) {
                    node->next = q.front();
                }
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
        }
        return root;
    }
};

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

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) {
            return root;
        }
        deque<Node*> q;
        if (root->left) {
            q.push_back(root->left);
        }
        if (root->right) {
            q.push_back(root->right);
        }
        while (!q.empty()) {
            int n = q.size();
            for (int i = 0; i < n; i ++) {
                Node *node = q.front();
                q.pop_front();
                if (i < n - 1) {
                    node->next = q.front();
                }
                if (node->left) {
                    q.push_back(node->left);
                }
                if (node->right) {
                    q.push_back(node->right);
                }
            }
        }
        return root;
    }
};

104.二叉树的最大深度

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        return 1 + max(maxDepth(root->left), maxDepth(root->right));
    }
};

111.二叉树的最小深度

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        if (root->left == nullptr) {
            return 1 + minDepth(root->right);
        }
        if (root->right == nullptr) {
            return 1 + minDepth(root->left);
        }
        return 1 + min(minDepth(root->left), minDepth(root->right));
    }
};

最后编辑于：2024.09.04 14:49:04

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 214,172评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,346评论 3赞 389
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 159,788评论 0赞 349
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,299评论 1赞 288
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,409评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,467评论 1赞 292
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,476评论 3赞 412
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,262评论 0赞 269
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,699评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,994评论 2赞 328
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,167评论 1赞 343
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,827评论 4赞 337
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,499评论 3赞 322
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,149评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,387评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,028评论 2赞 365
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,055评论 2赞 352

【代码随想录】day13

day13 二叉树1

二叉树定义

144.二叉树的前序遍历

145.二叉树的后序遍历

94.二叉树的中序遍历

102.二叉树的层序遍历

107.二叉树的层次遍历II

199.二叉树的右视图

637.二叉树的层平均值

429.N叉树的层序遍历

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

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

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

104.二叉树的最大深度

111.二叉树的最小深度

推荐阅读更多精彩内容