「算法刷题」二叉树的基础遍历相关的LeetCode题目实现

[TOC]

一、深度优先遍历

144. 二叉树的前序遍历（简单难度）

方法一：递归遍历法

class Solution {
public:
    vector<int> res;
    vector<int> preorderTraversal(TreeNode* root) {
        if(root==nullptr) return res;
        res.push_back(root->val);//前序位置插入
        preorderTraversal(root->left);
        preorderTraversal(root->right);
        return res;
    }
};

方法二：迭代遍历法

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==nullptr) return res;
        //根节点先入栈
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()){
            // 出栈
            TreeNode* cur=stk.top();
            stk.pop();
            //处理节点
            res.push_back(cur->val);
            //右入栈
            if(cur->right) stk.push(cur->right);
            //左入栈
            if(cur->left) stk.push(cur->left);
        }
        return res;
    }
};

方法三：分治思想

class Solution {
public:
    // 定义：输入二叉树，返回其前序遍历数组
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==nullptr) return res;
        // 获取左、右子树的前序遍历数组
        vector<int> leftRes=preorderTraversal(root->left);
        vector<int> rightRes=preorderTraversal(root->right);
        // 一棵二叉树的前序遍历结果 = 根节点 + 左子树的前序遍历结果 + 右子树的前序遍历结果
        res.push_back(root->val);
        res.insert(res.end(),leftRes.begin(),leftRes.end());
        res.insert(res.end(),rightRes.begin(),rightRes.end());
        return res;
    }
};

94. 二叉树的中序遍历（简单难度）

方法一：递归法

class Solution {
private:
    vector<int> res;
public:
    vector<int> inorderTraversal(TreeNode* root) {
        if(root==nullptr) return res;
        inorderTraversal(root->left);
        res.push_back(root->val);
        inorderTraversal(root->right);
        return res;
    }
};

方法二：迭代法

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==nullptr) return res;
        //根节点先入栈
        stack<TreeNode*> stk;
        TreeNode* cur=root;
        while(cur||!stk.empty()){
            // 存在
            if(cur){
                stk.push(cur);//入栈
                cur=cur->left;//换左边
            }
            // 不存
            else{
                cur=stk.top();//出栈
                stk.pop();
                // 处理节点
                res.push_back(cur->val);
                cur=cur->right;//换右边
            }
        }
        return res;
    }
};

145. 二叉树的后序遍历

方法一：递归法

class Solution {
private:
    vector<int> res;
public:
    vector<int> postorderTraversal(TreeNode* root) {
        if(root==nullptr) return res;
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        res.push_back(root->val);
        return res;
    }
};

方法二：迭代法

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if(root==nullptr) return res;
        //根节点先入栈
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()){
            // 出栈
            TreeNode* cur=stk.top();
            stk.pop();
            //处理节点
            res.push_back(cur->val);
            //左入栈
            if(cur->left) stk.push(cur->left);
            //右入栈
            if(cur->right) stk.push(cur->right);
        }
        reverse(res.begin(), res.end());// 反向
        return res;
    }
};

589. N 叉树的前序遍历（简单难度）

class Solution {
private:
    vector<int> res;
public:
    vector<int> preorder(Node* root) {
        if(root==nullptr) return res;
        res.push_back(root->val);
        for(Node* node:root->children)
            preorder(node);
        return res;
    }
};

590. N 叉树的后序遍历（简单难度）

class Solution {
private:
    vector<int> res;
public:
    vector<int> postorder(Node* root) {
        if(root==nullptr) return res;
        for(Node* node:root->children)
            postorder(node);
        res.push_back(root->val);
        return res;
    }
};

114. 二叉树展开为链表（中等难度）

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* pre=nullptr;
        if(root==nullptr) return ;
        //根节点先入栈
        stack<TreeNode*> stk;
        stk.push(root);
        while(!stk.empty()){
            // 出栈
            TreeNode* cur=stk.top();
            stk.pop();
            //处理节点
            if(pre) pre->right=cur;
            pre=cur;
            //右入栈
            if(cur->right) stk.push(cur->right);
            //左入栈
            if(cur->left) stk.push(cur->left);
        }
        pre=root;
        while(pre){
            pre->left=nullptr;
            pre=pre->right;
        }
    }
};

二、广度优先遍历

面试题32 - I. 从上到下打印二叉树（中等难度）

class Solution {
public:
    vector<int> levelOrder(TreeNode* root) {
        vector<int> res;
        if(root==NULL) return res;
        // 先入队 
        queue<TreeNode*> que;
        que.push(root);
        while(!que.empty()){
            // 出队
            TreeNode* cur=que.front();
            que.pop();
            // 处理节点
            res.push_back(cur->val);
            // 入队
            if(cur->left) que.push(cur->left);
            if(cur->right) que.push(cur->right);
        }
        return res;
    }
};

102. 二叉树的层序遍历（中等难度）

剑指 Offer 32 - II. 从上到下打印二叉树 II（中等难度）

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root==NULL) return result;
        //先入队
        queue<TreeNode*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            vector<int> level_result;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                TreeNode* cur=queue.front();
                queue.pop();
                //处理节点
                level_result.push_back(cur->val);
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
            //添加层数组
            result.push_back(level_result);
        }
        return result;
    }
};

107. 二叉树的层序遍历 II（中等难度）

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        if(root==NULL) return result;
        //先入队
        queue<TreeNode*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            vector<int> level_result;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                TreeNode* cur=queue.front();
                queue.pop();
                //处理节点
                level_result.push_back(cur->val);
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
            //添加层数组
            result.push_back(level_result);
        }
        reverse(result.begin(),result.end());
        return result;
    }
};

剑指 Offer 32 - III. 从上到下打印二叉树 III（中等难度）

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root==NULL) return result;
        //先入队
        queue<TreeNode*> queue;
        queue.push(root);
        bool isReverse=false;
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            vector<int> level_result;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                TreeNode* cur=queue.front();
                queue.pop();
                //处理节点
                level_result.push_back(cur->val);
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
            //添加层数组
            if(isReverse) reverse(level_result.begin(),level_result.end());
            isReverse = !isReverse;
            result.push_back(level_result);
        }
        return result;
    }
};

429. N 叉树的层序遍历（中等难度）

class Solution {
public:
    vector<vector<int>> levelOrder(Node* root) {
        vector<vector<int>> result;
        if(root==NULL) return result;
        //先入队
        queue<Node*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            vector<int> level_result;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                Node* cur=queue.front();
                queue.pop();
                //处理节点
                level_result.push_back(cur->val);
                //先左后右入队
                for(Node* node:cur->children){
                    if(node)   queue.push(node);
                }
            }
            //添加层数组
            result.push_back(level_result);
        }
        return result;
    }
};

103. 二叉树的锯齿形层序遍历（中等难度）

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root==nullptr) return res;
        bool flag=false;
        queue<TreeNode*>  que;
        que.push(root);
        while(!que.empty()){
            vector<int> level;
            int size=que.size();
            for(int i=0;i<size;++i){
                // 出栈
                TreeNode* cur=que.front();
                que.pop();
                // 处理
                level.push_back(cur->val);
                if(cur->left) que.push(cur->left);
                if(cur->right) que.push(cur->right);
            }
            if(flag)reverse(level.begin(), level.end());
            flag=!flag;
            res.push_back(level);
        }
        return res;
    }
};

199. 二叉树的右视图（中等难度）

剑指 Offer II 046. 二叉树的右侧视图（中等难度）

class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> result;
        if(root==NULL) return result;
        //先入队
        queue<TreeNode*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            vector<int> level_result;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                TreeNode* cur=queue.front();
                queue.pop();
                //处理节点
                level_result.push_back(cur->val);
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
            //添加层数组
            result.push_back(level_result.back());
        }
        return result;
    }
};

515. 在每个树行中找最大值（中等难度）

剑指 Offer II 044. 二叉树每层的最大值（中等难度）

class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        vector<int> result;
        if(root==NULL) return result;
        //先入队
        queue<TreeNode*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            int level_max=INT_MIN;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                TreeNode* cur=queue.front();
                queue.pop();
                //处理节点
                level_max=max(level_max,cur->val);
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
            //添加层数组
            result.push_back(level_max);
        }
        return result;
    }
};

513. 找树左下角的值（中等难度）

剑指 Offer II 045. 二叉树最底层最左边的值（中等难度）

class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        vector<vector<int>> result;
        if(root==NULL) return -1;
        //先入队
        queue<TreeNode*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            vector<int> level_result;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                TreeNode* cur=queue.front();
                queue.pop();
                //处理节点
                level_result.push_back(cur->val);
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
            //添加层数组
            result.push_back(level_result);
        }
        return result.back()[0];
    }
};

637. 二叉树的层平均值（简单难度）

class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> result;
        if(root==NULL) return result;
        //先入队
        queue<TreeNode*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            double level_sum=0.0;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                TreeNode* cur=queue.front();
                queue.pop();
                //处理节点
                level_sum+=cur->val;
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
            //添加层数组
            result.push_back(level_sum/size);
        }
        return result;
    }
};

116. 填充每个节点的下一个右侧节点指针（中等难度）

117. 填充每个节点的下一个右侧节点指针 II（中等难度）

class Solution {
public:
    Node* connect(Node* root) {
        if(root==NULL) return root;
        //先入队
        queue<Node*> queue;
        queue.push(root);
        //队不为空就遍历
        while(!queue.empty()){
            //更新当前队列大小
            int size = queue.size();
            //层数组
            //vector<int> level_result;
            Node* pre=NULL;
            //遍历当前队列（正好存储当前层元素）
            for(int i=0;i<size;i++){
                //出队
                Node* cur=queue.front();
                queue.pop();
                //处理节点
                if(pre) pre->next=cur;
                pre=cur;
                //先左后右入队
                if (cur->left)queue.push(cur->left);
                if (cur->right)queue.push(cur->right);
            }
        }
        return root;
    }
};