代码随想录day14 LeetCode 144.二叉树的前序遍历 145.二叉树的后序遍历 94.二叉树的中序遍历 二叉树的链式存储结构创建

144. 二叉树的前序遍历

class Solution {
public:
    vector<int> v;
    vector<int> preorderTraversal(TreeNode* root) {
    
        if(root==NULL)return v;
        v.push_back(root->val);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
        return v;
    }
};

145. 二叉树的后序遍历

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

94. 二叉树的中序遍历

class Solution {
public:
    vector<int>result;
    vector<int> inorderTraversal(TreeNode* root) {
        if(root==NULL)return result;
        inorderTraversal(root->left);
        result.push_back(root->val);
        inorderTraversal(root->right);
        return result;
    }
};

class BiTreeNode {
public:
    char  data;                    //数据域
    BiTreeNode  *leftChild,  *rightChild,* parent;    //左右子树亲树指针
    BiTreeNode():leftChild(NULL), rightChild(NULL){}
    ~BiTreeNode() {}
};

class BiTree {
public:
    int size;
    BiTreeNode *root;    //根结点指针
    string sTree;        //建树字符串
    int pos;            //标识建树字符串的当前字符位置
    int deep;
    char datatemp;
    char datatemp1;
    char datatemp2;
    int distanceMax;
    BiTreeNode* CreateTree();
    void deepCount(BiTreeNode  *t,int height);
    void distanceCount(BiTreeNode *t);
    BiTree():root(NULL) {};
    void Create(string vArray);    //建树公有接口，参数是特定的先序遍历字符串
    void levelOrder(BiTreeNode* t){
        queue<BiTreeNode*>tq;
        BiTreeNode* p=t;
        if(p!=NULL)tq.push(p);
        while(!tq.empty()){
            cout<<tq.front()->data;
            if(tq.front()->leftChild)tq.push(tq.front()->leftChild);
            if(tq.front()->rightChild)tq.push(tq.front()->rightChild);
            tq.pop();
        }
    }
};
//二叉树公有接口的实现
void BiTree::Create(string vArray)
{    pos=0;
    size=0;
    deep=0;
    distanceMax=0;
    sTree.assign(vArray);    //把参数保存到内部字符串
    root = CreateTree();    //建树成功后root指向根结点
}

BiTreeNode * BiTree::CreateTree(){
    BiTreeNode* t;
    char ch=sTree[pos++];
    if(ch=='#')t=NULL;
    else{
        size++;
        t=new BiTreeNode();
        t->data=ch;
        t->leftChild=CreateTree();
        if(t->leftChild)t->leftChild->parent=t;
        t->rightChild=CreateTree();
        if(t->rightChild)t->rightChild->parent=t;
    }
    return t;
}