leetcode 106. Construct Binary Tree from Inorder and Postorder Traversal 中后序构造BST

冷不防 2022-06-08 04:11 103阅读 0赞

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

题意很简答，就是根据中序遍历和后序遍历来构造二叉搜索树BST，直接递归去做。

查询index可以使用map做查询。建议和上一道题[ leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal 中前序构造BST][leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal _BST]和[leetcode 449. Serialize and Deserialize BST 二叉搜索树BST的序列化和反序列化][leetcode 449. Serialize and Deserialize BST _BST]一起学习。

建议和[leetcode 87. Scramble String 字符串拼凑 && DFS深度优先搜索][leetcode 87. Scramble String _ _ DFS] 和 [leetcode 95. Unique Binary Search Trees II 递归构造所有可能的搜索二叉树BST + 卡特兰数][leetcode 95. Unique Binary Search Trees II _BST _] 一起学习，因为做法类似

这道题可以和[leetcode 108. Convert Sorted Array to Binary Search Tree 构建平衡二叉搜索树 + DFS][leetcode 108. Convert Sorted Array to Binary Search Tree _ _ DFS] 一起学习

建议和[leetcode 331. Verify Preorder Serialization of a Binary Tree 二叉树的前序序列验证][leetcode 331. Verify Preorder Serialization of a Binary Tree] 和 [leetcode 654. Maximum Binary Tree 构造最大二叉树][leetcode 654. Maximum Binary Tree] 和[leetcode 297. Serialize and Deserialize Binary Tree 二叉树的序列化和反序列化 + 深度优先遍历DFS][leetcode 297. Serialize and Deserialize Binary Tree _ _ _DFS]一起学习

代码如下：

class TreeNode 
    {
        
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
    }
    
    /*
     * 直接递归解决
     * */
    public class Solution 
    {
        
        public TreeNode buildTree(int[] inorder, int[] postorder) 
        {
            if(inorder==null || inorder.length<=0 ||postorder==null || postorder.length<=0 || inorder.length!=postorder.length)
                return null;
            else
                return getRootByRecursion(inorder,postorder,inorder.length-1,0,inorder.length-1);
        }
    
        //递归生成二叉树
        TreeNode getRootByRecursion(int[] inorder, int[] postorder,int postEnd, int inStart, int inEnd) 
        {
            if(inStart > inEnd)
                return null;
            else
            {
                //后续的第一个节点就是父节点
                TreeNode root=new TreeNode(postorder[postEnd]);
                //或许在中序中的index
                int index=getIndexInOrder(inorder,root.val);
                //lenLeft是左子树的元素数量
                int lenLeft=(index-1)-inStart +1;
                //lenRight是右子树的元素数量
                int lenRight=(inEnd-inStart + 1) -lenLeft -1;
    
                //递归生成左右子树
                if(lenLeft>0)
                    root.left=getRootByRecursion(inorder,postorder,  postEnd-lenRight-1, inStart, index-1);
                if(lenRight>0)
                    root.right=getRootByRecursion(inorder,postorder, postEnd-1, index+1, inEnd);
                return root;
            }
        }
    
        //在中序中查找下标，这里也可以使用map来实现查表
        int getIndexInOrder(int[] inorder, int val)
        {
            for(int i=0;i<inorder.length;i++)
            {
                if(val==inorder[i])
                    return i;
            }
            return -1;
        }
    }

下面是C++的做法，和上一道题一模一样，不过把前序遍历换成了后序遍历，就是递归解决

代码如下：

#include <iostream>
    #include <vector>
    #include <algorithm>
    
    
    using namespace std;
    
    /*
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    */
    
    class Solution 
    {
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder)
        {
            if (inorder.size() <= 0)
                return NULL;
            else
                return getAll(postorder, inorder, postorder.size()-1, 0, inorder.size() - 1);
        }
    
        TreeNode* getAll(vector<int>& p, vector<int>& i,int pbeg,int ibeg,int iend)
        {
            if (ibeg > iend)
                return NULL;
            else
            {
                int index = getIndex(i, p[pbeg]);
                int leftLen = (index - 1) - ibeg + 1;
                int rightLen = (iend - ibeg + 1) - leftLen - 1;
    
                TreeNode* root = new TreeNode(p[pbeg]);
                root->left = getAll(p, i, pbeg -rightLen - 1, ibeg, index - 1);
                root->right = getAll(p, i, pbeg - 1, index+1, iend);
                return root;
            }
        }
    
        int getIndex(vector<int>& a, int target)
        {
            for (int i = 0; i < a.size(); i++)
            {
                if (a[i] == target)
                    return i;
            }
            return 0;
        }
    };

[leetcode 105. Construct Binary Tree from Preorder and Inorder Traversal _BST]: http://blog.csdn.net/jackzhang_123/article/details/77977697
[leetcode 449. Serialize and Deserialize BST _BST]: http://blog.csdn.net/jackzhang_123/article/details/78760997
[leetcode 87. Scramble String _ _ DFS]: http://blog.csdn.net/JackZhang_123/article/details/77942734
[leetcode 95. Unique Binary Search Trees II _BST _]: http://blog.csdn.net/JackZhang_123/article/details/77948273
[leetcode 108. Convert Sorted Array to Binary Search Tree _ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/77978036
[leetcode 331. Verify Preorder Serialization of a Binary Tree]: http://blog.csdn.net/jackzhang_123/article/details/78151329
[leetcode 654. Maximum Binary Tree]: http://blog.csdn.net/jackzhang_123/article/details/78865619
[leetcode 297. Serialize and Deserialize Binary Tree _ _ _DFS]: http://blog.csdn.net/jackzhang_123/article/details/78122376