LeetCode 105/106 Construct Binary Tree from Preorder/Postorder and Inorder Traversal

红太狼 2022-08-07 13:35 112阅读 0赞

一：LeetCode 105 [Construct Binary Tree from Preorder and Inorder Traversal][]

题目：

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:  
You may assume that duplicates do not exist in the tree.

链接：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

分析：此题就是由二叉树的前序和中序遍历的结果构建这颗二叉树

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        void createTree(TreeNode *p, vector<int> &preorder, int pstart, int pend, vector<int> &inorder, int istart, int iend, int flag){
            if(pstart > pend) return;
            p = new TreeNode(preorder[pstart]);
            if(root == NULL) root = pNode = p;
            else{
                if(flag) pNode->right = p;     //  主要是将这颗树连接起来
                else pNode->left = p;
                pNode = p;
            }
            if(pstart == pend) return;
            int i = istart;
            for(; i <= iend; i++){
                if(inorder[i] == preorder[pstart])break;
            }
            int k = i - istart;    // 左子树有多少个元素
            createTree(p->left, preorder, pstart+1, pstart+k, inorder, istart, i-1, 0);   // 创建左子树 flag=0表示创建左子树
            pNode = p;                    
            createTree(p->right, preorder, pstart+k+1, pend, inorder, i+1, iend, 1);     // 创建右子树 flag=1表示创建右子树
        }
        
        TreeNode *buildTree(vector<int> &preorder, vector<int> &inorder) {
            root = NULL;
            pNode = NULL;
            int n = preorder.size();
            if(n == 0) return root;
            createTree(root, preorder, 0, n-1, inorder, 0, n-1, 0);
            return root;
            
        }
    private:
        TreeNode *root, *pNode;
    };

二：LeetCode106 [Construct Binary Tree from Inorder and Postorder Traversal][]

题目：

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:  
You may assume that duplicates do not exist in the tree.

链接：https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

分析：此题是由中序和后序遍历的结果构建二叉树

/**
     * Definition for binary tree
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        void createTree(TreeNode *p, vector<int> &inorder, int istart, int iend, vector<int> &postorder, int pstart, int pend, int flag){
            if(pstart > pend) return;
            p = new TreeNode(postorder[pend]);
            if(root == NULL) root = pNode = p;
            else{
                if(flag) pNode->right = p;    //  将这颗树连接起来
                else pNode->left = p;
                pNode = p;
            }
            if(pstart == pend) return;
            int i = istart;
            for(; i<= iend; i++){
                if(inorder[i] == postorder[pend]) break;
            }
            int k = i - istart;
            createTree(p->left, inorder, istart, i-1, postorder, pstart, pstart+k-1, 0);   // 创建左子树
            pNode = p;
            createTree(p->right, inorder, i+1, iend, postorder, pstart+k, pend-1, 1);   // 创建右子树
            
        }
        TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
            root = pNode = NULL;
            int n = inorder.size();
            if(n == 0) return root;
            createTree(root, inorder, 0, n-1, postorder, 0, n-1, 0);
            return root;
            
            
        }
    private:
        TreeNode *root, *pNode;
    
    };

[Construct Binary Tree from Preorder and Inorder Traversal]: https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
[Construct Binary Tree from Inorder and Postorder Traversal]: https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/