Skip to content

Latest commit

 

History

History
347 lines (330 loc) · 9.72 KB

二叉树的遍历.md

File metadata and controls

347 lines (330 loc) · 9.72 KB

二叉树理论基础

  1. 满二叉树：顾名思义就是二叉树的所有节点都是有值的，没有空节点，如果二叉树深度为 $k$，那么满二叉树有 $2^k-1$ 个节点
  2. 完全二叉树：除了最底层节点没有填满外，其余每层节点都填满了，且最底层节点一定是从左到右填
  3. 二叉搜索树：二叉搜索树的中序遍历是从小到大排序的
    • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
    • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
    • 它的左、右子树也分别为二叉排序树
  4. 平衡二叉搜索树：平衡二叉搜索树要么是空树，要么其左右两个子树的高度差不超过 $1$，并且左右两个子树都是平衡二叉搜索树
    C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树
  5. 二叉树的遍历方式：
    • 前序遍历（根节点->左子树->右子树）
    • 中序遍历（左子树->根节点->右子树）
    • 后序遍历（左子树->右子树->根节点）
    • 层序遍历
  6. 二叉树的定义：
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x): val(x), left(NULL), right(NULL) {}
}*root;

二叉树的前中后序遍历（递归）

前序遍历

vector <int> res;

vector<int> main(TreeNode* root){
    dfs(root);
    return res;
}

void dfs(TreeNode* root){
    if (!root) return;
    res.push_back(root->val);
    dfs(root->left);
    dfs(root->right); 
}

中序遍历

vector <int> res;

vector<int> main(TreeNode* root){
    dfs(root);
    return res;
}

void dfs(TreeNode* root){
    if (!root) return;
    dfs(root->left);
    res.push_back(root->val);
    dfs(root->right); 
}

后序遍历

vector <int> res;

vector<int> main(TreeNode* root){
    dfs(root);
    return res;
}

void dfs(TreeNode* root){
    if (!root) return;
    dfs(root->left);
    dfs(root->right); 
    res.push_back(root->val);
}

二叉树的前中后序遍历（迭代）

前序遍历

  • 思路：二叉树的迭代遍历一般用栈来存储
    1. 初始化栈
    2. 当前节点赋值为根节点
    3. 将根节点和所有左子树入栈并加入答案直至当前节点为空
    4. 每弹出一个栈顶元素就到达当前节点的右子树
  • 代码模板 1
stack<TreeNode*> stk;
vector<int> res;

auto cur = root;
while (cur || stk.size()){
    while (cur){
        res.push_back(cur->val);
        stk.push(cur);
        cur = cur->left;
    }
    auto tmp = stk.top();
    stk.pop();
    cur = tmp->right;
}
  • 代码模板 2
stack<TreeNode*> stk;
vector<int> res;

if (root) stk.push(root);
while (stk.size()){
    auto cur = stk.top();
    stk.pop();
    res.push_back(cur->val);
    if (cur->right) stk.push(cur->right);
    if (cur->left) stk.push(cur->left);
}

中序遍历

  • 思路：与前序遍历的模板 1 相似，区别是前序遍历中在找树的左底部的过程中记录答案，而中序遍历是找到左底部再开始记录答案
  • 代码模板
stack<TreeNode*> stk;
vector<int> res;

auto cur = root;
while (cur || stk.size()){
    while (cur){
        stk.push(cur);
        cur = cur->left;
    }
    auto tmp = stk.top();
    stk.pop();
    res.push_back(tmp->val);
    cur = tmp->right;
}

后序遍历

  • 思路：与前序遍历的模板 1 类似
    栈是先进后出的顺序，如果是后序遍历，输出为左->右->中，和前序遍历中->左->右相比，可以在前序遍历的基础上将输入改为中->右->左，再将答案数组反转即为左->右->中
  • 代码模板 1
stack<TreeNode*> stk;
vector<int> res;

auto cur = root;
while (cur || stk.size()){
    while (cur){
        stk.push(cur);
        res.push_back(cur->val);
        cur = cur->right;
    }
    auto tmp = stk.top();
    stk.pop();
    cur = tmp->left;
}
reverse(res.begin(), res.end());
  • 代码模板 2
    与前序遍历的代码模板 2 类似
stack<TreeNode*> stk;
vector<int> res;

if (root) stk.push(root);
while (stk.size()){
    auto cur = stk.top();
    stk.pop();
    res.push_back(cur->val);
    if (cur->left) stk.push(cur->left);
    if (cur->right) stk.push(cur->right);
}

二叉树的层序遍历

  • 思路：二叉树的前中后序遍历都是用深度优先搜索的方法（dfs）主要使用栈实现，层序遍历是广度优先搜索主要使用队列实现
  • 常规解法：
    1. 初始化队列
    2. 将根节点加入队列中
    3. 当队列不为空时，弹出队头元素，加入到答案中
    4. 如果左子树非空，左子树加入队列
    5. 如果右子树非空，右子树加入队列
  • 代码模板
queue<TreeNode*> q;
vector<int> res;

q.push(root);
while (q.size()){
    int n = q.size();
    for (int i = 0; i < n; i ++){
        auto cur = q.front();
        q.pop();
        res.push_back(cur->val);
        if (cur->left) q.push(cur->left);
        if (cur->right) q.push(cur->right); 
    }
}

二叉树遍历有关的题目

leetcode.144 二叉树的前序遍历

leetcode.94 二叉树的中序遍历

leetcode.145 二叉树的后序遍历

leetcode.226 反转二叉树

  • 链接https://leetcode.cn/problems/invert-binary-tree/
  • 解题方法：有三种方法解本道题
    从上到下遍历树的时候翻转左右节点->前序遍历
    遍历到树的叶子节点回溯的时候翻转左右节点->后序遍历
    遍历每一层，将每一层的左右节点翻转->层序遍历
  • leetcode解题代码
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        // 递归（终止条件）
        if (!root) return root;
        // 前序遍历（递归解法）
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        // 递归返回值
        return root;
    }
};

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        // 递归（终止条件）
        if (!root) return root;
        // 后序遍历（递归解法）
        invertTree(root->left);
        invertTree(root->right);
        swap(root->left, root->right);
        // 递归返回值
        return root;
    }
};

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        // 层序遍历模板
        queue<TreeNode*> q;
        if (root) q.push(root);
        while (q.size()){
            int n = q.size();
            for (int i = 0; i < n; i ++){
                auto c = q.front();
                q.pop();
                swap(c->left, c->right);
                if (c->left) q.push(c->left);
                if (c->right) q.push(c->right);
            }
        }
        return root;
    }
};

leetcode.589 N 叉树的前序遍历

class Solution {
public:
    vector<int> res;
    vector<int> preorder(Node* root) {
        // 递归终止条件
        if (!root) return res;
        // 前序遍历
        res.push_back(root->val);
        for (auto c: root->children) preorder(c);
        return res;
    }
};

class Solution {
public:
    vector<int> preorder(Node* root) {
        // 与前序遍历常规解法相似
        stack<Node*> stk;
        vector<int> res;
        if (root) stk.push(root);
        while (stk.size()){
            auto c = stk.top();
            stk.pop();
            res.push_back(c->val);
            for (int i = c->children.size() - 1; i >= 0; i --){
                stk.push(c->children[i]);
            }
        }
        return res;
    }
};

leetcode.590 N 叉树的后序遍历

class Solution {
public:
    vector<int> res;
    vector<int> postorder(Node* root) {
        // 递归终止条件
        if (!root) return res;
        // 后序遍历
        for (auto c: root->children) postorder(c);
        res.push_back(root->val);
        return res;
    }
};

class Solution {
public:
    vector<int> postorder(Node* root) {
        // 与后序遍历常规解法类似
        stack<Node*> stk;
        vector<int> res;
        if (root) stk.push(root);
        while (stk.size()){
            auto c = stk.top();
            stk.pop();
            res.push_back(c->val);
            for (int i = 0; i < c->children.size(); i ++){
                stk.push(c->children[i]);
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};