Leetcode: Construct Binary Tree from Inorder and Postorder Traversal

迈不过友情╰ 2022-08-07 11:48 17阅读 0赞

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

Note:  
You may assume that duplicates do not exist in the tree.  
根据二叉树的中序遍历和后续遍历结果构造二叉树。

思路分析：  
这道题和上道题《[ Leetcode: Construct Binary Tree from Preorder and Inorder Traversal ][Leetcode_ Construct Binary Tree from Preorder and Inorder Traversal]》的思路类似。  
二叉树后序遍历的最后一个节点是根节点。  
在中序遍历中找出根节点，由根节点分开，中序遍历左边是左子树中序遍历结果（设有X个节点），右边是右子树遍历结果（设有Y个节点）。  
后序遍历除去最后一个根节点，数X节点，这X个节点是左子树后序遍历的结果，剩下节点（肯定是Y个）是右子树后序遍历结果。  
这样我们就得到了左右子树的后序遍历和中序遍历的结果了，所以又回到了原来的问题。

C++参考代码：

/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
    class Solution {
    private:
        TreeNode *makeNode(vector<int>::iterator inBegin, vector<int>::iterator inEnd, vector<int>::iterator postBegin, vector<int>::iterator postEnd)
        {
            if (postBegin == postEnd) return nullptr;
            //从中序遍历结果中找出根节点（根节点在后序遍历中是最后一个节点）
            vector<int>::iterator itRoot = find(inBegin, inEnd, *(postEnd - 1));
            TreeNode *root = new TreeNode(*itRoot);
            //计算根的左子树节点个数
            int leftSize = itRoot - inBegin;
            //在中序遍历结果中根节点的左边是左子树中序遍历结果，右边是右子树中序遍历结果
            //在后序遍历结果中除去根节点前leftSize个节点是左子树前序遍历结果，后面的节点是右子树前序遍历结果
            root->left = makeNode(inBegin, itRoot, postBegin, postBegin + leftSize);
            root->right = makeNode(itRoot + 1, inEnd, postBegin + leftSize, postEnd - 1);
            return root;
        }
    
    public:
        TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
        {
            if (postorder.empty()) return nullptr;
            TreeNode *root = makeNode(inorder.begin(), inorder.end(), postorder.begin(), postorder.end());
            return root;
        }
    };

Java参考代码：

/** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */
    public class Solution { 
        private TreeNode makeNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
            if (postBegin == postEnd) return null;
            int index = 0;
            for (int i = inBegin; i < inEnd; i++) {
                if (inorder[i] == postorder[postEnd - 1]) {
                    index = i;
                }
            }
            int leftSize = index - inBegin;
            TreeNode root = new TreeNode(postorder[postEnd - 1]);
            root.left = makeNode(inorder, inBegin, inBegin + leftSize, postorder, postBegin, postBegin + leftSize);
            root.right = makeNode(inorder, index + 1, inEnd, postorder, postBegin + leftSize, postEnd - 1);
            return root;
        }
    
        public TreeNode buildTree(int[] inorder, int[] postorder) {
            if (postorder.length == 0) return null;
            TreeNode root = makeNode(inorder, 0, inorder.length, postorder, 0, postorder.length);
            return root;
        }
    }

[Leetcode_ Construct Binary Tree from Preorder and Inorder Traversal]: http://blog.csdn.net/theonegis/article/details/44860563