2020-02-28发表2024-03-31更新算法竞赛6 分钟读完 (大约960个字)

二叉树存储与遍历模板

本文由简悦 SimpRead 转码，原文地址 www.acwing.com

二叉树, 模板, 遍历, dfs,bfs

二叉树存储与遍历模板

二叉树的存储与遍历

const int N = 1e6 + 10;

// 二叉树的存储,l数组为左节点,r数组为右结点
int l[N], r[N];
// 存储节点的数据
char w[N];
// 节点的下标指针
int idx = 0;

// 先序创建
int pre_create(int n) {
    cin >> w[n];
    if (w[n] == '#') return -1;
    l[n] = pre_create(++idx);
    r[n] = pre_create(++idx);
    return n;
}

// 中序创建
int in_create(int n) {
    if (w[n] == '#') return -1;
    l[n] = in_create(++idx);
    cin >> w[n];
    r[n] = in_create(++idx);
    return n;
}

// 后序创建
int back_create(int n) {
    if (w[n] == '#') return -1;
    l[n] = back_create(++idx);
    r[n] = back_create(++idx);
    cin >> w[n];
    return n;
}

// 先序遍历
void pre_print(int n){
    if (w[n] != '#') cout << w[n] << ' ';
    if (l[n] > 0) pre_print(l[n]);
    if (r[n] > 0) pre_print(r[n]);
}

// 中序遍历
void in_print(int n){
    if (l[n] > 0) in_print(l[n]);
    if (w[n] != '#') cout << w[n] << ' ';
    if (r[n] > 0) in_print(r[n]);
}

// 后序遍历
void back_print(int n){
    if (l[n] > 0) back_print(l[n]);
    if (r[n] > 0) back_print(r[n]);
    if (w[n] != '#') cout << w[n] << ' ';
}

// 层序遍历
void bfs(int root){
    queue<int> que;
    que.push(root);
    while (!que.empty()) {
        int t = que.front();
        cout << w[t] << ' ';
        que.pop();
        if (l[t] > 0 && w[l[t]] != '#')
            que.push(l[t]);
        if (r[t] > 0 && w[r[t]] != '#')
            que.push(r[t]);
    }
}

应用

int main(){
    // 先序创建
    pre_create(++idx);
    // 中序创建
    // in_create(++idx);
    // 后序创建
    // back_create(++idx);
    // 先序遍历
    pre_print(1);
    // 中序遍历
    in_print(1);
    // 后序遍历
    back_print(1);
    // 层序遍历
    bfs(1);
    // 测试数据abc##de#g##f###
    // 输出如下：
    // a b c d e g f 
    // c b e g d f a 
    // c g e f d b a 
    // a b c d e f g 
    return 0;
}

留着自己用

二叉树的中序遍历

// 递归代码

/**
 * 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) {}
 * };
 */
class Solution {
public:

    void dfs(TreeNode*u,vector<int>&res) {
        if(!u) return ;
        dfs(u->left,res);
        res.push_back(u->val);
        dfs(u->right,res);
    }

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

镜像二叉树

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。数据范围：树中节点数量 [0,100]。

样例
如下图所示二叉树[1,2,2,3,4,4,3,null,null,null,null,null,null,null,null]为对称二叉树：
    1
   / \
  2   2
 / \ / \
3  4 4  3

如下图所示二叉树[1,2,2,null,4,4,3,null,null,null,null,null,null]不是对称二叉树：
    1
   / \
  2   2
   \ / \
   4 4  3

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return dfs(root->left,root->right);
    }
    
    bool dfs(TreeNode *p,TreeNode *q) {
        if(!p || !q) return !p && !q;
        if(p->val != q->val) return false;
        return dfs(p->left,q->right) && dfs(p->right , q->left);
    }
};

二叉搜索树的范围和

给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。

https://www.acwing.com/video/2838/
https://www.acwing.com/activity/content/problem/content/4215/

**示例 1：**
输入：root = [10,5,15,3,7,null,18], low = 7, high = 15
输出：32
        10
       /  \
      5    15
     / \     \
    3   7    18

**示例 2：**
输入：root = [10,5,15,3,7,13,18,1,null,6], low = 6, high = 10
输出：23
       10
      /  \
     5    15
    / \   / \
   3   7 13  18
  /   /
 1   6

提示：

树中节点数目在范围 [1, 2 * 104] 内
1 <= Node.val <= 105
1 <= low <= high <= 105
所有 Node.val 互不相同

/**
 * 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) {}
 * };
 */
class Solution {
public:
    int rangeSumBST(TreeNode* root, int low, int high) {
        if (!root) return 0;
        int val = root->val;
        if (val >= low && val <= high)
            return val + rangeSumBST(root->left, low, high) + rangeSumBST(root->right, low, high);
        else if (val < low)
            return rangeSumBST(root->right, low, high);
        else
            return rangeSumBST(root->left, low, high);
    }
};