二叉树的一些基本操作

佚名 4年前 (2020-02-09) 算法 670人围观抢沙发百度已收录

数据结构的一些知识很久没碰了，忘得差不多了都，来回顾总结一下，本篇先写一下二叉树相关的一些操作。

二叉树定义

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

二叉树的创建

通过输入先序二叉树序列创建二叉树，用'#'字符代表空节点。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

//通过先序输入创建二叉树
TreeNode* CreateTreeByInput()
{
    char ch;
    std::cin >> ch;
    if (ch == '#')
        return NULL;//输入#表示创建结束
    TreeNode* root = new TreeNode(ch);
    root->left = CreateTreeByInput();
    root->right = CreateTreeByInput();
    return root;
}

二叉树的遍历

先序、中序、后序三种基本遍历方式。

//先序遍历
void PreOrder(TreeNode* root)
{
    if (root == NULL)return;
    std::cout << (char)root->val << ' ';
    PreOrder(root->left);
    PreOrder(root->right);
}
//中序遍历
void InOrder(TreeNode* root)
{
    if (root == NULL)return;
    PreOrder(root->left);
    std::cout << (char)root->val << ' ';
    PreOrder(root->right);
}
//后序遍历
void PostOrder(TreeNode* root)
{
    if (root == NULL)return;
    std::cout << (char)root->val << ' ';
    PreOrder(root->left);
    PreOrder(root->right);
}

还有一种层次遍历方式，从上往下逐层遍历，需要借助队列实现，每次将父结点出队，子结点进队即可。

//层次遍历
void levelOrder(TreeNode* root)
{
    if (root == NULL)return;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty())
    {
        TreeNode* now = q.front();
        cout << (char)now->val << ' ';
        if (now->left != NULL)q.push(now->left);
        if (now->right != NULL)q.push(now->right);
        q.pop();
    }
}

LeetCode上一道题目：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
要求得到自底向上的层次遍历序列，只需要先按层次遍历得到序列，然后用头插法插入最终集合即可。

class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> result;
        if(root==NULL)return result;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            vector<int> level;
            int cnt=q.size();
            for(int i=0;i<cnt;i++)
            {
                TreeNode* node=q.front();
                q.pop();
                level.push_back(node->val);
                if(node->left!=NULL)q.push(node->left);
                if(node->right!=NULL)q.push(node->right);
            }
            result.insert(result.begin(),level);
        }
        return result;
    }
};

二叉树序列化与反序列化

序列化就是指将二叉树转换成一个序列(比如字符串)，反序列化就是将转换的序列还原成二叉树。

序列化

没啥好说的，按照先序遍历依次写入字符串。

//序列化二叉树(先序)，结果保存在str中
void Serialize(TreeNode* root, std::string& str)
{
    if (root == NULL)
    {
        str += "#";
        return;
    }
    str += (char)root->val;
    Serialize(root->left, str);
    Serialize(root->right, str);
}

反序列化

反序列化就是按照先序遍历创建的同时，用index索引来从字符串中读取当前结点对应字符。

//反序列化方法(先序)
TreeNode* Deserialize(const std::string str, int& index)
{
    if (str == "" && index >= str.size())return NULL;
    if (str[index] == '#')
    {
        index++;
        return NULL;
    }
    TreeNode* root = new TreeNode(str[index++]);
    root->left = Deserialize(str, index);
    root->right = Deserialize(str, index);
    return root;
}

//调用反序列化
    string str = "akjl#####";
    int index = 0;
    TreeNode* root=Deserialize(str, index);

求二叉树最大深度(层数)

//二叉树最大深度
int MaxDepth(TreeNode* root)
{
    if (root == NULL)return 0;
    return max(MaxDepth(root->left), MaxDepth(root->right)) + 1;
}

二叉树所有路径

题目：https://leetcode-cn.com/problems/binary-tree-paths/
深搜完事，碰到叶子结点就说明找到一条路径，加入结果集合，否则就继续搜。

class Solution {
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> res;
        dfs(root,"",res);
        return res;
    }

    void dfs(TreeNode* root,string str,vector<string> &res)
    {
        if(root!=NULL)
        {
            str+=to_string(root->val);
            if(root->left==NULL&&root->right==NULL)
            {
                res.push_back(str);return;
            }
            dfs(root->left,str+"->",res);
            dfs(root->right,str+"->",res);
        }
    }
};