二叉树遍历

1.层次遍历（广度优先遍历）

用队列实现，队首出队，队首的子节点入队。

1,二叉树的层次遍历, 打印

void levelTraverse(TreeNode* root){
    if(!root)  return;

    queue<TreeNode*> nodes;
    nodes.push(root);

    while(!nodes.empty()){
        TreeNode* p=nodes.front();
        cout<<p->val<<' ';  //打印队首
        if(p->left)
            nodes.push(p->left); //队首左右子节点入队
        if(p->right)
            nodes.push(p->right); 
        nodes.pop();   //队首出队
    }
}

2,二叉树的层次遍历，分行打印

void leveltraverse(treenode *root){
    if(!root) return;

    queue<treenode*> que;
    que.push_back(root);

    while(!que.empty()){
        int len=que.size(); //该行节点数
        for(int i=0;i<len;i++){  //该行节点都出队列，下一行节点均进队列
            treenode *p=que.front();
            que.pop();
            cout<<p->val<<" ";
            if(p->left)
                que.push(p->left);
            if(p->right)
                que.push(p->right);
        }
        cout<<endl;
    }
}

2.深度优先遍历（先序遍历）

1,二叉树的深度遍历（递归）, 打印

void preOrderTraverse(TreeNode* root){
    if(root){
        cout<<root->val<<' ';
        preOrderTraverse(root->left);
        preOrderTraverse(root->right); 
    }
}

2,二叉树的深度遍历（递归）, 打印各条路径
需要一个栈来存储路径，会搜索所有路径，最后栈为空

void preOrderTraverse(TreeNode* root,vector<int>& path){
    if(root){
        path.push_back(root->val);
        
        if(!root->left && !root->right){//若该节点是叶节点，打印该路径
            for(vector<int>::iterator iter=path.begin();iter!=path.end();iter++)
                cout<<*iter<<' ';
            cout<<endl;
            path.pop_back(); 
            return;
        }
        //不是叶节点，遍历它的子节点
        preOrderTraverse(root->left,path);
        preOrderTraverse(root->right,path);
        path.pop_back(); //该节点访问完后，出栈
    }
}

3.先序遍历

void preorderTraversal(TreeNode *root)
{
    stack<TreeNode *> s;
    TreeNode *p = root; //p来遍历

    while(p || !s.empty())
    {
        while(p)  //从根节点开始：打印,入栈,左走
        {
            cout<<p->val<<' ';
            s.push(p);
            p = p->left;
        }
        if(!s.empty()) //p为空，即栈顶左孩子为空：p指向栈顶的右孩子，栈顶出栈
        {
            TreeNode * temp = s.top();
            p = temp->right;
            s.pop();
        }
    }
}

4.中序遍历

void inorderTraversal(TreeNode *root)
{
    stack<TreeNode *> s;
    TreeNode *p = root;

    while(p || !s.empty())
    {
        while(p) //从根节点开始：入栈,左走
        {
            s.push(p);
            p = p->left;
        }
        if(!s.empty()) //p为空，即栈顶左孩子为空：打印栈顶，p指向栈顶的右孩子，栈顶出栈
        {
            TreeNode * temp = s.top();
            cout<<temp->val;
            p = temp->right;
            s.pop();
        }
    }
}

先序和中序遍历风格相似，但是实际上前者是在指针迭代时访问结点值，后者是在栈顶访问结点值。

5.后序遍历

void postorderTraversal(TreeNode *root)
{
    stack<TreeNode *> s;
    TreeNode *p = root , *r=NULL;//r为右子树是否被访问过的标记

    while(p || !s.empty())
    {
        while(p) //从根节点开始：入栈,左走
        {
            s.push(p);
            p = p->left;
        }
        if(!s.empty()) //p为空，即栈顶左孩子为空
        {
            TreeNode * temp = s.top();
            if(temp->right && temp->right!=r;) //栈顶的右子树存在，且未被访问，p指向栈顶的右孩子
                p=temp->right;
            else{   //栈顶左子树不存在，右子树不存在或访问过，则访问栈顶，栈顶出栈
                cout<<temp->val<<' ';
                s.pop();
                r=temp; //记录最近访问过的节点
            }
        }
    }
}

也是通过栈顶访问节点值

6.查找某个值

TreeNode* findnode(TreeNode* root, int k){
    if(root){
        if(root->val==k) //根节点
            return root;

        TreeNode* target=findnode(root->left);//根节点找不到，左子树找
        if(target)
            return target;
        target=findnode(root->right);//左子树，根节点都找不到，右子树找
           return target;
    }
    return NULL; //空树，返回null
}

7.序列化二叉树

前序中序后序遍历都可以

//1，序列化
    string serialize(TreeNode* root) {
        string s;
        if(!root)
            s+="#,"; //以逗号为分隔符，例如：10,20,30,#,#,
        else
        {
            s+=to_string(root->val);
            s+=",";
            s+=serialize(root->left);
            s+=serialize(root->right);
        }
        return s;
    }
//2，反序列化
    TreeNode* deserialize(string s, int &i) { //调用时i=0
        string s_temp;
        while(s[i]!=','){
            s_temp.push_back(s[i++]);
        }
        i++;

        if(s_temp=="#"){
            return NULL;
        }
        else{
            int value = atoi(s_temp.c_str());
            TreeNode *root = new TreeNode(value);
            root->left=deserialize(s,i);
            root->right=deserialize(s,i);
            return root;
        }
    }