二叉树遍历与构造

二叉树的遍历

  二叉树遍历其实很简单，三种遍历都是一样的，只不过顺序先后不一样罢了。

先序遍历

  访问根结点，先序遍历左子树，先序遍历右子树

void PreOrder(BitTree T){
    if( T != nullptr){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

中序遍历

  中序遍历左子树，访问根结点，中序遍历右子树

void InOrder(BitTree T){
    if(T != nullptr){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

后序遍历

后序遍历左子树，后序遍历右子树，访问根结点

void PostOrder(BitTree T){
    if( T != nullptr ){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

  时间复杂度都为O（n），在递归遍历中，递归工作栈的栈深恰好为树的深度，在最坏情况下，二叉树是有n个结点且深度为 n 的单支树，遍历算法的空间复杂度为O（n）。

利用非递归方式遍历二叉树

  借助栈，可以将二叉树的递归遍历转换为非递归算法。以中序遍历为例，给出中序遍历非递归算法。先扫描（并非访问）根结点的所有左结点并将它们一一进栈，然后出栈一个结点*p，访问它。然后继续扫描该结点的右孩子结点，将其进栈，在扫描该孩子结点的所有左结点并一一进栈，如此继续，直到栈空。

  中序遍历的非递归算法如下：

void InOrderWithoutRecursion(BitTree T){
    Stack<BitTree> S;           //辅助栈
    BitTree p = T;                //遍历指针
    while( p || !IsEmpty(S) ){    //栈不为空或p不为空时
        if( p ){                
            S.push(p);            //根指针进栈
            p = p->lchild;        //遍历左子树
        }else{
            S.pop(p);            //根指针退栈
            visit(p);            //cout << p->data;
            p = p->rchild;      //向右子树走
        }
    }    
}

  前序遍历的非递归算法：

void PreOrderWithoutRecursion(BitTree T)
{
    if (T == nullptr)
        return;
    BTNode* p = T;
    stack<BitNode*> s;
    while (!s.empty() || p)
    {
        if (p)
        {
            visit(p);        // cout << p->data;
            s.push(p);
            p = p->lchild;
        }
        else
        {
            p = s.top();
            s.pop();
            p = p->rchild;
        }
    }
    cout << endl;
}

  后序遍历的非递归算法：后序遍历的难点在于：需要判断上次访问的节点是位于左子树，还是右子树。若是位于左子树，则需跳过根节点，先进入右子树，再回头访问根节点；若是位于右子树，则直接访问根节点。直接看代码，代码中有详细的注释。

void PostOrderWithoutRecursion(BTNode* root)
{
    if (root == NULL)
        return;
    stack<BTNode*> s;
    //pCur:当前访问节点，pLastVisit:上次访问节点
    BTNode* pCur, *pLastVisit;
    //pCur = root;
    pCur = root;
    pLastVisit = NULL;
    //先把pCur移动到左子树最下边
    while (pCur)
    {
        s.push(pCur);
        pCur = pCur->lchild;
    }
    while (!s.empty())
    {
        //走到这里，pCur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
        pCur = s.top();
        s.pop();
        //一个根节点被访问的前提是：无右子树或右子树已被访问过
        if (pCur->rchild == NULL || pCur->rchild == pLastVisit)
        {
            cout << setw(4) << pCur->data;
            //修改最近被访问的节点
            pLastVisit = pCur;
        }
        /*这里的else语句可换成带条件的else if:
        else if (pCur->lchild == pLastVisit)//若左子树刚被访问过，则需先进入右子树(根节点需再次入栈)
        因为：上面的条件没通过就一定是下面的条件满足。仔细想想！
        */
        else
        {
            //根节点再次入栈
            s.push(pCur);
            //进入右子树，且可肯定右子树一定不为空
            pCur = pCur->rchild;
            while (pCur)
            {
                s.push(pCur);
                pCur = pCur->lchild;
            }
        }
    }
    cout << endl;
}

  层次遍历

  层次遍历需要借助队列。先将二叉树根结点入队，然后初岁，访问该结点，若它有左子树，则将左子树根节点入队；若它有右子树，则将右子树根结点入队。然后出队，对出队结点访问，如此反复，直到队列为空。

void LevelOrder(BitTree T){
    if( T == nullptr){
        return ;
    }
    Queue<BitNode*> q;                    //辅助队列
    q.push(T);                            //将根结点入队    
    while(!q.empty()){                    //队列不为空时
        int sz = q.size();                
        for(int i = 0; i < sz; i++){
            BitNode* cur = Q.front();    
            q.pop();                    //队头元素出队    
            if(p->lchild != nullptr){
                q.push(p->lchild);        //左子树不为空时，左子树入队
            }
            if(p->rchild != nullptr){
                q.push(p->rchild);        //右子树不为空时，右子树入队
            }
        }
    }
}

由遍历序列构造二叉树

  由二叉树的先序和中序序列可以唯一确定一棵二叉树，同样后序和中序序列也可以唯一确定一棵二叉树，但先序和后序不能确定一棵二叉树。

先序和中序序列构造一棵二叉树

  思路：我们知道先序序列的第一个值其实就是根节点的值，这样我们就可以在中序序列中找到对应的根节点，那么根节点左边的数就全为左子树的结点，根节点右边的数就全为右子树的结点。根据这个想法，再递归的进行构造，见代码。

/**
 * 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 {
private:
    unordered_map<int, int> index;  //借助哈希表，让我们快速的找到分割点，不用每次都去循环一遍
public:
    TreeNode* myBuildTree(const vector<int>& preorder, const vector<int>& inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return nullptr;
        }
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = index[preorder[preorder_root]];

        // 先把根节点建立出来
        TreeNode* root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root->left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root->right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();
        // 构造哈希映射，帮助我们快速定位根节点
        for (int i = 0; i < n; ++i) {
            index[inorder[i]] = i;
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
};

后序和中序序列构造一棵二叉树

  思路：我们知道后序序列的最后一个值其实就是根节点的值，这样我们就可以在中序序列中找到对应的根节点，那么根节点左边的数就全为左子树的结点，根节点右边的数就全为右子树的结点。根据这个想法，再递归的进行构造，见代码。

class Solution {
private:
    unordered_map<int,int> index; //借助哈希表，让我们快速的找到分割点，不用每次都去循环一遍
public:
    TreeNode* myBuildTree(vector<int>& postorder,vector<int>& inorder,int postorder_left,int postorder_right,int inorder_left,int inorder_right){
        if(postorder_left > postorder_right){
            return nullptr;
        }
        //后序遍历的最后一个节点其实就是根节点
        int postorder_root = postorder_right;
        //在中序遍历中定位根节点
        int inorder_root = index[postorder[postorder_root]];
        //先建立根节点
        TreeNode* root=new TreeNode(postorder[postorder_root]);
        //得到左子树节点数量
        int size_left_subtree=inorder_root-inorder_left;
        //注意区间边界范围 +1，-1 一定要注意判别好
        //递归构造左右子树
        root->left=myBuildTree(postorder,inorder,postorder_left,postorder_left+size_left_subtree-1,inorder_left,inorder_root-1);
        root->right=myBuildTree(postorder,inorder,postorder_left+size_left_subtree,postorder_root-1,inorder_root+1,inorder_right);
        return root;
    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder){
        int n=postorder.size();
        //借助哈希表，让我们快速的找到分割点，不用每次都去循环一遍
        for(int i=0;i<n;i++){
            index[inorder[i]]=i;
        }
        return myBuildTree(postorder,inorder,0,n-1,0,n-1);
    }
};