关注

算法训练营第十三天：二叉树基础

算法训练营第十三天|

二叉树理论基础

  • 二叉树类型有：满二叉树、完全二叉树、二叉搜索树和平衡二叉搜索树。
  • 存储方式有：链式存储（指针）和顺序存储（数组）。
  • 遍历方式有：
    1. 深度优先：前中后序遍历（递归，迭代）
    2. 广度优先：层序遍历（迭代）
  • 二叉树结点的定义
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };

二叉树的递归遍历

卡哥文字以及视频讲解链接

重点

  • 二叉树的学习引入了递归的大量使用
  • 递归三要素：
    1. 确定递归函数的参数和返回值
    2. 确定终止条件
    3. 确定单层递归的逻辑
  • 递归开销大，内存占用久

c++实现（前序遍历）中，左，右

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        // if(root == nullptr) return {};三处注释搭配使用，起到递归函数中的终止条件作用
        vector<int> result;
        travalTree(root, result);
        return result;
    }
    void travalTree(TreeNode* root, vector<int>& result){//这个引用很重要
        if(root == nullptr) return;//终止条件
        result.push_back(root -> val);//中
        /*if(root -> left)*/ travalTree(root -> left, result);//左孩子
        /*if(root -> right)*/ travalTree(root -> right, result);//右孩子
        return;
    }
};

c++实现（中序遍历）左，中，右

class Solution {
public:
    std::vector<int> preorderTraversal(TreeNode* root) {
        std::vector<int> result;
        traverse(root, result);
        return result;
    }
private:
    void traverse(TreeNode* node, std::vector<int>& res) {
        if (node == nullptr) return;//递归终止条件
        traverse(node->left,  res);//左
        res.push_back(node->val);//中
        traverse(node->right, res);//右
    }
};

c++实现（后序遍历）左，右，中

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

二叉树的迭代遍历

卡哥文字以及视频讲解链接

重点

  • 手动实现一遍，按照实现步骤转换成代码，就理解了
  • 就是一个栈，放进放出。
  • 只用栈，所有的循环判断依靠的是栈本身。弹出顺序和使用顺序一致。
  • 中序遍历使用一个栈无法实现，就是因为栈顶节点和要使用节点不一致。循环判断条件依靠的是帮助指定的指针和栈本身。

c++实现（前序遍历）中，左，右

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;
        vector<int> result;
        if(root == nullptr) return result;//检查非空，防止越界
        st.push(root);//和while条件搭配
        while(!st.empty()){
            TreeNode* temp = st.top();
            st.pop();
            result.push_back(temp -> val);
            //栈的特点，先进后出，所以要先使用就要后放。先放右，再放左
            if(temp -> right) st.push(temp -> right);
            if(temp -> left) st.push(temp -> left);
        }
        return result;
    }
};

c++实现（中序遍历）左，中，右

一直向左走到底（入栈），遇到空就弹出栈顶（即“回溯”），访问该节点，然后转向其右子树。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        TreeNode* cur = root;
        //这个循环是为了使用cur
        while(cur != NULL || !st.empty()){
            if(cur != nullptr){
                st.push(cur);
                cur = cur -> left;//左
            }else{
                cur = st.top();
                st.pop();
                result.push_back(cur -> val);//中
                cur = cur -> right;//右
            }
        }
        return result;
    }
};
  • 因为栈放进去之后，所有元素都没有区别，只有栈顶获取，弹出，所以需要另一个指针来确定栈顶的元素是否要使用

c++实现（后序遍历）左，右，中

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if(root == nullptr) return result;
        st.push(root);
        while(!st.empty()){
            TreeNode* temp = st.top();
            st.pop();
            result.push_back(temp -> val);
            //因为要保证使用顺序是先中，所以把左右中看作中右左的逆序。
            if(temp -> left) st.push(temp -> left);
            if(temp -> right) st.push(temp -> right);
        }
        //整体反转
        reverse(result.begin(), result.end());
        return result;
    }
};

二叉树的统一迭代法

卡哥文字以及视频讲解链接

重点

  • 两种方法
  • 第一种，一个节点可以处理的范围是自己和左右孩子（该节点的根，该节点处理不到）。节点分两部分完成遍历，第一次通过节点来获得左右孩子，第二次看到第一次处理过的标志直接处理本节点。
  • 第二种，给一个pair，first表示节点，second表示是否使用过。
  • 本质是一种方式，就是让节点分两步进行。没处理过的先处理，处理过的直接用。

c++实现 （前序遍历）使用null表示使用

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if(root == nullptr) return {};//检查非空
        st.push(root);//还是和while搭配
        while(!st.empty()){
            TreeNode* temp = st.top();
            //每次进入首先获取栈顶元素
            if(temp){
                st.pop();
                //因为是前序，需要弹出重新排一下序
                if(temp -> right) st.push(temp -> right);
                if(temp -> left) st.push(temp -> left);
                st.push(temp);
                st.push(nullptr);
                //在要使用元素后加一个 NULL 表示这个节点和周围的父子关系已经实现过了，下一次就是使用
            }else{
                //栈顶为空，弹出，获得新栈顶，使用
                st.pop();
                temp = st.top();
                st.pop();
                result.push_back(temp -> val);
            }
        }
        return result;
    }
};

c++实现 (中序遍历）使用null表示使用

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

c++实现 (后序遍历）使用null表示使用

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if(root == nullptr) return {};
        st.push(root);
        while(!st.empty()){
            TreeNode* temp = st.top();
            if(temp){
            //这里不用弹出
                st.push(nullptr);
                if(temp -> right) st.push(temp -> right);
                if(temp -> left) st.push(temp -> left);
            }else{
                st.pop();
                temp = st.top();
                st.pop();
                result.push_back(temp -> val);
            }
        }
        return result;
    }
};

c++实现 (中序遍历）使用 pair 携带一个bool来确定元素状态

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<pair<TreeNode*, bool>> st;
        if (root != nullptr)
            st.push(make_pair(root, false)); // 多加一个参数，false 为默认值，含义见下文注释

        while (!st.empty()) {
            auto node = st.top().first;
            auto visited = st.top().second; //多加一个 visited 参数，使“迭代统一写法”成为一件简单的事
            st.pop();

            if (visited) { // visited 为 True，表示该节点和两个儿子位次之前已经安排过了，现在可以收割节点了
                result.push_back(node->val);
                continue;
            }

            // visited 当前为 false, 表示初次访问本节点，此次访问的目的是“把自己和两个儿子在栈中安排好位次”。
            
            // 中序遍历是'左中右'，右儿子最先入栈，最后出栈。
            if (node->right)
                st.push(make_pair(node->right, false));
            
            // 把自己加回到栈中，位置居中。
            // 同时，设置 visited 为 true，表示下次再访问本节点时，允许收割。
            st.push(make_pair(node, true));

            if (node->left)
                st.push(make_pair(node->left, false)); // 左儿子最后入栈，最先出栈
        }
        
        return result;
    }
};

二叉树层序遍历

卡哥文字以及视频讲解链接

重点

  • 逐层

c++实现

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        vector<vector<int>> result;
        if(root == nullptr) return result;
        que.push(root);
        while(!que.empty()){
            int size = que.size();
            vector<int> vec;
            for(int i = 0 ; i < size ; i++){
                TreeNode* temp = que.front();
                que.pop();
                vec.push_back(temp -> val);
                if(temp -> left) que.push(temp -> left);
                if(temp -> right) que.push(temp -> right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

一个重点

  • 也是特点吧
  • 遍历的时候，如果单一使用栈或者队列，函数体内的循环逻辑围绕的就是栈或队列是否为空
  • 如果是中序迭代，遍历需要一个指针来辅助，函数体内的循环逻辑围绕的就是栈是否空以及指针是否为空
  • 这样便于记忆二叉树的遍历逻辑

坚持就是胜利

日期天次题目
01-2613深度优先、广度优先
  • 第十三天，搞定！
author
轩

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/yizhan_tian/article/details/157400312

评论

赞0

评论列表

微信小程序
QQ小程序

关于作者

点赞数：0
关注数：0
粉丝：0
文章：0
关注标签：0
加入于：--