二叉树的遍历与建立 – 树结构基础

二叉树

二叉树结构如下

    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
    };

二叉树的层序遍历实质是 BFS算法

三种顺序的二叉树遍历实质是 DFS的二叉递归树调用轨迹

基于 递归 或 迭代 思想加以调整，二叉树相关问题均可得到解决

二叉树遍历

层序遍历

    void levelOrder(Node *root)
    {
        if(!root) return;
        queue<Node *> q;
        q.push(root);
        while(!q.empty())
        {
            Node *x = q.front();
            q.pop();
            operation(x);
            q.push(x->left);
            q.push(x->right);
        }
    }

按层遍历

    void levelOrder(Node *root)
    {
        if(!root) return;
        queue<Node *> q;
        q.push(root);
        while(!q.empty())
        {
            int n = q.size();
            for(int i = 0; i < n; i++)
            {
                Node *x = q.front();
                q.pop();
                operation(x);
                if(x->left) q.push(x->left);
                if(x->right) q.push(x->right);
            }
        }
    }

三种遍历思想

自顶向下 处理时核心操作置于 前序 处理

自底向上 处理时核心操作置于 后序 处理

前序遍历

递归

    void traverse(Node *root)
    {
        if(root != nullptr)
        {
            preOperation();
            traverse(root -> left);
            traverse(root -> right);
        }
    }

迭代

    void traverse(Node *root)
    {
        if(root != nullptr)
        {
            stack<Node *> stk;
            Node *node = root;
            while(!stk.empty() || node != nullptr)
            {
                while(node != nullptr)
                {
                    preOperation();
                    stk.push(node);
                    node = node -> left;
                }

                node = stk.top();
                stk.pop();
                node = node -> right;
            }
        }

        else return;
    }

中序遍历

递归

    void traverse(Node *root)
    {
        if(root != nullptr)
        {
            traverse(root -> left);
            inOperation();
            traverse(root -> right);
        }
    }

迭代

后序遍历

递归

    void traverse(Node *root)
    {
        if(root != nullptr)
        {
            traverse(root -> left);
            traverse(root -> right);
            postOperation();
        }
    }

迭代

建立二叉树

前序和中序建立二叉树

递归

    vector<int> preorder = {1, 2, 4, 8, 9, 5, 10, 3, 6, 7, 11};
    vector<int> inorder  = {8, 4, 9, 2, 5, 10, 1, 6, 3, 11, 7};

    TreeNode *buildTree()
    {
        int n = preorder.size();
        if (n <= 0) return nullptr;
        return build(0, 0, n - 1);
    }

    TreeNode *build(int pStart, int iStart, int iEnd)
    {
        if (iStart > iEnd) return nullptr;

        int rVal = preorder[pStart];
        int i = iStart;
        while (inorder[i] != rVal) i++;
        int lNum = i - iStart;

        TreeNode *left = build(pStart + 1, iStart, i - 1);
        TreeNode *right = build(pStart + lNum + 1, i + 1, iEnd);
        return new TreeNode(rVal, left, right);
    }

迭代

后序和中序建立二叉树

递归

    vector<int> postorder = {8, 9, 4, 10, 5, 2, 6, 11, 7, 3, 1};
    vector<int> inorder   = {8, 4, 9, 2, 5, 10, 1, 6, 3, 11, 7};

    TreeNode *buildTree()
    {
        int n = postorder.size();
        if (n <= 0) return nullptr;
        return build(n - 1, 0, n - 1);
    }

    TreeNode *build(int pEnd, int iStart, int iEnd)
    {
        if (iStart > iEnd) return nullptr;

        int rVal = postorder[pEnd];
        int i = iEnd;
        for (; inorder[i] != rVal; i--);
        int rNum = iEnd - i;

        TreeNode *left = build(pEnd - rNum - 1, iStart, i - 1);
        TreeNode *right = build(pEnd - 1, i + 1, iEnd);
        return new TreeNode(rVal, left, right);
    }

迭代