构造二叉树

本文分别介绍了通过二叉树的前序和中序遍历结果构造二叉树以及通过二叉树的中序和后序遍历结果构造二叉树。

定义二叉树结构

// Definition for a binary tree node.
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

从前序与中序遍历序列构造二叉树

class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return build(preorder, 0, preorder.size()-1,
                     inorder, 0, inorder.size()-1);  
    }
    TreeNode* build(vector<int> preorder, int preStart, int preEnd,
                    vector<int> inorder, int inStart, int inEnd){
                        // base case;
                        if(preStart>preEnd){
                            return nullptr;
                        }
                        //root节点对应的值就是前序遍历数组的第一个元素；
                        int rootVal = preorder[preStart];
                        //rootVal在中序遍历数组中的索引；
                        int index = 0;
                        for(int i=inStart;i<=inEnd;i++){
                            if(inorder[i] == rootVal){
                                index=i;
                                break;
                            }
                        }
                        int size = index-inStart;
                        //先构造出当前根节点；
                        TreeNode* root = new TreeNode(rootVal);
                        //递归构造左右子树；
                        root->left = build(preorder,preStart+1, preStart+size,
                                         inorder,inStart,index-1);
                        root->right = build(preorder, preStart+size+1, preEnd,
                                         inorder,index+1,inEnd);
                        return root;
                   }
};

func buildTree(preorder []int, inorder []int) *TreeNode {
    return build(preorder, 0, len(preorder)-1,
                 inorder, 0, len(inorder)-1)
}

func build(preorder []int, preStart int, preEnd int,
           inorder []int, inStart int, inEnd int) *TreeNode {
    // base case;
    if preStart > preEnd {
        return nil
    }
    //root节点对应的值就是前序遍历数组的第一个元素；
    rootVal := preorder[preStart]
    //rootVal在中序遍历数组中的索引；
    index := 0
    for i := inStart; i <= inEnd; i++ {
        if inorder[i] == rootVal {
            index = i
            break
        }
    }
    size := index - inStart
    //先构造出当前根节点；
    root := &TreeNode{Val: rootVal}
    //递归构造左右子树；
    root.Left = build(preorder, preStart+1, preStart+size,
                      inorder, inStart, index-1)
    root.Right = build(preorder, preStart+size+1, preEnd,
                       inorder, index+1, inEnd)
    return root
}

从后序与中序遍历序列构造二叉树

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        return build(inorder, 0, inorder.size()-1,
                     postorder, 0, postorder.size()-1);
    }
    TreeNode* build(vector<int> inorder, int inStart, int inEnd,
                    vector<int> postorder, int postStart, int postEnd){
                        // base case;
                        if(postStart>postEnd){
                            return nullptr;
                        }
                        //root节点对应的值就是后序遍历数组的最后一个元素；
                        int rootVal = postorder[postEnd];
                        //rootVal在中序遍历数组中的索引；
                        int index = 0;
                        for(int i=inStart; i<=inEnd; i++){
                            if(inorder[i]==rootVal){
                                index = i;
                                break;
                            }
                        }
                        int size = index-inStart;
                        //先构造出当前根节点；
                        TreeNode* root = new TreeNode(rootVal);
                        //递归构造左右子树；
                        root->left = build(inorder, inStart, index-1,
                                           postorder, postStart, postStart+size-1);
                        root->right = build(inorder, index+1, inEnd,
                                            postorder, postStart+size, postEnd-1);
                        return root; 
                    }
};

func buildTree(inorder []int, postorder []int) *TreeNode {
    return build(inorder, 0, len(inorder)-1,
                 postorder, 0, len(postorder)-1)
}

func build(inorder []int, inStart int, inEnd int,
           postorder []int, postStart int, postEnd int) *TreeNode {
    // base case;
    if postStart > postEnd {
        return nil
    }
    //root节点对应的值就是后序遍历数组的最后一个元素；
    rootVal := postorder[postEnd]
    //rootVal在中序遍历数组中的索引；
    index := 0
    for i := inStart; i <= inEnd; i++ {
        if inorder[i] == rootVal {
            index = i
            break
        }
    }
    size := index - inStart
    //先构造出当前根节点；
    root := &TreeNode{Val: rootVal}
    //递归构造左右子树；
    root.Left = build(inorder, inStart, index-1,
                      postorder, postStart, postStart+size-1)
    root.Right = build(inorder, index+1, inEnd,
                       postorder, postStart+size, postEnd-1)
    return root
}