代码随想录算法训练营第14天 | 二叉树理论基础，二叉树遍历

二叉树理论基础

一个节点指向左右两个孩子节点构成的树状结构。

二叉树的种类

• 满二叉树

一棵二叉树只有度为0和度为2的节点，且度为0的节点都在同一层上时，该二叉树为满二叉树。深度为k的满二叉树，节点一定有\(2 ^k - 1\)个。

满二叉树，图源代码随想录

• 完全二叉树

除了最底层节点可能没填满以外，每层节点都达到了最大值，且最底层节点都集中在左侧。

完全二叉树

• 二叉搜索树

二叉搜索树是个有序树，其左子树上的节点的值均小于根节点的值，右子树上的值均大于根节点的值，且左右子树也是二叉搜索树。

二叉搜索树

• 平衡二叉搜索树

平衡二叉搜索树实在二叉搜索树的基础上，添加以下要求：

• 为空树或者左右子树高度差不大于1
• 左右子树都是平衡二叉搜索树

平衡二叉搜索树

C++中map, set, multimap, multiset的底层实现都是平衡二叉搜索树，所以map, set的增删操作时间都是\(O(logn)\)。unordered_set、unordered_map 的实现是哈希表。

二叉树的存储方式

可以链式存储，也可以顺序存储

• 链式存储

使用链表的形式，通过左右孩子指针完成链接。

链式存储二叉树

• 顺序存储

就是使用数组来存储二叉树。若父节点的索引为\(i\)，其左孩子节点索引为\(2 * i + 1\)，右孩子节点索引为\(2 * i + 2\)。

二叉树的遍历方式

• 深度优先遍历

优先向深度递增的方向访问。可分为前序遍历、中序遍历、后序遍历。

• 广度优先遍历

优先访问同一深度的节点。有层次遍历。

二叉树的定义

struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
};

二叉树递归遍历

例题:

• 前序遍历

• 中序遍历

• 后序遍历

递归遍历的写法比较简单，按照前中后三种遍历方式的定义来写即可。

前序遍历：

class Solution {
private:
    void preOrderTravel(TreeNode *root, vector<int> &result) {
        if (root == NULL) return;
        result.push_back(root -> val);          // 先访问该节点
        preOrderTravel(root -> left, result);   // 再访问左右节点
        preOrderTravel(root -> right, result);
    }
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == NULL) return result;
        preOrderTravel(root, result);
        return result;
    }
};

中序遍历:

class Solution {
private:
    void inOrderTravel(TreeNode *root, vector<int> &result) {
        if (!root) return;
        inOrderTravel(root -> left, result);    // 先访问左节点
        result.push_back(root -> val);          // 再访问中间节点
        inOrderTravel(root -> right, result);   // 最后访问右节点
    }
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        inOrderTravel(root, result);
        return result;
    }
};

后序遍历:

class Solution {
private:
    void postOrderTravel(TreeNode *root, vector<int> &result) {
        if (root == NULL) return;
        postOrderTravel(root -> left, result);  // 先访问左节点
        postOrderTravel(root -> right, result); // 再访问右节点
        result.push_back(root -> val);          // 最后访问中间节点
    }
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        postOrderTravel(root, result);
        return result;
    }
};

二叉树迭代遍历

使用迭代来完成二叉树的遍历也是一个重点.二叉树的迭代遍历中,最主要的部分是对栈的调用.

前序遍历:

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == NULL) return result;
        stack<TreeNode*> st;                            // 用来遍历节点的栈
        st.push(root);                                  // 将根节点入栈
        while (!st.empty()) {                           // 栈不为空时
            TreeNode *node = st.top();                  // 取栈顶并出栈
            st.pop();
            result.push_back(node -> val);              // 访问节点
            if (node -> right) st.push(node -> right);  // 左右子节点存在时,先压入右子节点,再压入左子节点
            if (node -> left) st.push(node -> left);
        }
        return result;
    }
};

中序遍历:

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        stack<TreeNode*> st;
        TreeNode* cur = root;                   // 中序遍历中处理顺序和访问顺序不一致,需要额外指针辅助
        while (cur != NULL || !st.empty()) {    // 当指针不为空或者栈不为空时
            if (cur) {                          // 如果指针不为空
                st.push(cur);                   // 指针节点压栈,指针左移
                cur = cur -> left;
            } else {                            // 若指针为空,意味着遇到了一颗子树遍历完成,需要进行中间节点的访问
                cur = st.top();
                st.pop();
                result.push_back(cur -> val);
                cur = cur -> right;             // 访问中间节点完毕后,指针右移
            }
        }
        return result;
    }
};

后序遍历:

后序遍历的顺序是左右中,可以通过中右左的顺序逆转来完成.

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if (!root) return result;
        stack<TreeNode*> st;
        st.push(root);
        while (!st.empty()) {                       // 与前序遍历的代码相似,不过交换了左右节点的压栈顺序
            TreeNode *cur = st.top();
            st.pop();
            result.push_back(cur -> val);
            if (cur -> left) st.push(cur -> left);
            if (cur -> right) st.push(cur -> right);
        }
        reverse(result.begin(), result.end());      // 逆转访问记录来获得目标顺序的记录
        return result;
    }
};

二叉树统一迭代法

上面的迭代法写的方式不够统一. 下面是三种遍历比较统一的写法.

前序遍历:

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == NULL) return result;
        stack<TreeNode*> st;
        st.push(root);                                      // 压入根节点
        while (!st.empty()) {                               // 栈不为空时
            TreeNode *node = st.top();                      // 取栈顶
            if (node) {                                     // 若栈顶元素不是空指针,则弹出并将不为空的右指针和左指针压入
                st.pop();
                if (node -> right) st.push(node -> right);
                if (node -> left) st.push(node -> left);
                st.push(node);                              // 再压入节点本身
                st.push(NULL);                              // 压入一个空指针,表示需要访问该节点
            } else {                                        // 栈顶是空指针时
                st.pop();
                node = st.top();                            // 获得需要访问的节点并进行访问
                st.pop();
                result.push_back(node -> val);
            }
        }
        return result;
    }
};

中序遍历:

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == NULL) return result;
        stack<TreeNode*> st;
        st.push(root);                                      // 压入根节点
        while (!st.empty()) {                               // 栈不为空时
            TreeNode *node = st.top();                      // 取栈顶
            if (node) {                                     // 若栈顶元素不是空指针,则弹出并将不为空的右指针,节点指针和访问标记,左指针压入
                st.pop();
                if (node -> right) st.push(node -> right);
                st.push(node);                              // 压入节点本身
                st.push(NULL);                              // 压入一个空指针,表示需要访问该节点
                if (node -> left) st.push(node -> left); 
            } else {                                        // 栈顶是空指针时
                st.pop();
                node = st.top();                            // 获得需要访问的节点并进行访问
                st.pop();
                result.push_back(node -> val);
            }
        }
        return result;
    }
};

后序遍历:

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        if (root == NULL) return result;
        stack<TreeNode*> st;
        st.push(root);                                      // 压入根节点
        while (!st.empty()) {                               // 栈不为空时
            TreeNode *node = st.top();                      // 取栈顶
            if (node) {                                     // 若栈顶元素不是空指针,则弹出并将节点指针和访问标记,不为空的右指针,左指针压入
                st.pop();
                st.push(node);                              // 压入节点本身
                st.push(NULL);                              // 压入一个空指针,表示需要访问该节点
                if (node -> right) st.push(node -> right);
                if (node -> left) st.push(node -> left); 
            } else {                                        // 栈顶是空指针时
                st.pop();
                node = st.top();                            // 获得需要访问的节点并进行访问
                st.pop();
                result.push_back(node -> val);
            }
        }
        return result;
    }
};