讨论/《二叉树》 - 从中序与后序遍历序列构造二叉树/
《二叉树》 - 从中序与后序遍历序列构造二叉树
共 19 个回复

不行。仅有前序遍历 后序遍历,没办法区分左右子树的节点。
中序遍历有其特殊性:找到root节点后可以区分左右子树。

6

对于后序遍历,最后一个元素必为根
我们只要找到最后一个元素在中序遍历中的位置就可以将数组一分为二,
左侧为左子树的遍历结果,右侧为右子树
对拆分后的两个数组递归的进行上述操作即可

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int len=inorder.length;
        if(len==0)return null;
        return dfs(inorder,postorder,0,len-1,0,len-1);
    }

    TreeNode dfs(int[] inorder, int[] postorder,int head1,int tail1, int head2,int tail2){
        if(head2>tail2)return null;
        
        int val=postorder[tail2];
        TreeNode root=new TreeNode(val);
        if(head2==tail2)return root;

        int mid=0;  //拆分点mid的位置是相对的,因为h1!=h2
        while(inorder[head1+mid]!=val)mid++;

        root.left=dfs(inorder, postorder, head1, head1+mid-1, head2, head2+mid-1);
        root.right=dfs(inorder, postorder, head1+mid+1, tail1, head2+mid, tail2-1);

        return root;
    }
}

同理,对于已知前序遍历和中序遍历构造二叉树的问题也可使用此方法解决。

思考:已知前序遍历和后续遍历能否构造出唯一的二叉树?如果能,如何构造?如果不能请说明理由。

9

效率不高,但我说一下我的思路,表达可能不算明朗,望指正。
寻找特点(不一定有用):
1.中序第一位和后序第一位都是最左叶子节点
2.后序最后一位是根节点,且后序最后第二位是根节点右子树的根节点
3.中序可以通过根节点分为左右两棵子树

通过2、3
a.我们根据根节点可以区分中序数组中当前范围的左右子树,
b.后续数组倒着看,获取后序倒数第二位的根节点【注意:所有的叶子节点其实都可以看作是根节点,只不过他的左右子树是null。
c.如果他的右子树范围不为空,那么这个点是他的右子树的根。反之,如果他的左子树不为空,这个点是他的左子树的根,如果这个根节点左右范围都没有,那他就是叶子节点。
d.当范围重合为一个点时,这个点就是叶子节点。
e.不管是右根节点,左根节点,还是叶子节点,你用了以后到要从后序数组最后“删除它”(就是不要他了,没利用价值了)。

由此可以递归,每次获得根节点,区分左右树,先构建右子树,再构建左子树,建一个子节点,从后序数组中删除它。

/**
 * 时间:23.93% 内存:58.80%
 * */
private int rootIndex;
public TreeNode buildTree(int[] inorder, int[] postorder) {
    if(inorder.length!=postorder.length){
        return null;
    }
    rootIndex = postorder.length-1;
    return buildTree(inorder, postorder,0,inorder.length-1);
}

private TreeNode buildTree(int[] inorder,int[] postorder,int left,int right){
    if(rootIndex<0 || left>right){
        return null;
    }
    if(left == right){
        rootIndex--;
        return new TreeNode(inorder[left]);
    }
    int i;
    for (i = left; i <= right; i++) {
        if(inorder[i]==postorder[rootIndex]){
            rootIndex--;
            break;
        }
    }
    TreeNode node = new TreeNode(inorder[i]);
    node.right = buildTree(inorder,postorder,i+1,right);
    node.left = buildTree(inorder,postorder,left,i-1);
    return node;
}
2

如果存在值相同的节点怎么办,比如[1,2,2],这放到map里面会丢一个的

2
class Solution {
    /*
     * 后续遍历的最后一个数字是根节点
     * 中序遍历的根节点,左边是左子树,右边是右子树
     */

    int[] mPostorder; //后序遍历结果
    HashMap<Integer,Integer> memo = new HashMap<Integer,Integer>();//中序遍历中val值对应位置
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        mPostorder = postorder;
        for(int i = 0 ; i<inorder.length ; i++){
            memo.put(inorder[i],i);
        }
        return buildTree(0 , inorder.length - 1 , 0 , postorder.length - 1);
    }

    /*
     * 中序: 左 根 右
     * 后续: 左 右 根
     */
    public TreeNode buildTree(int inorderStart , int inorderEnd , int postorderStart,int postorderEnd){
        if(inorderStart > inorderEnd || postorderStart > postorderEnd){
            return null;
        }
        int val = mPostorder[postorderEnd]; //根节点
        int rootIndex = memo.get(val); //根节点在中序中的位置

        TreeNode root = new TreeNode(val);
        root.left = buildTree(inorderStart , rootIndex - 1 , 
        postorderStart , postorderStart + (rootIndex - 1) - inorderStart );//后续的end = 后续start + 中序左子树长度(中序end - 中序start))

        root.right = buildTree(rootIndex + 1 , inorderEnd , 
        postorderEnd - 1 - (inorderEnd - (rootIndex +1))  , postorderEnd -1); //后续的start = 后续end - 中序右子树长度(中序end - 中序start)
        return root; 
    }
}
2

因为malloc不会自动生成构造函数

1

题目中给出

注意:
你可以假设树中没有重复的元素。

1
var buildTree = (inorder, postorder) => {
    const len = inorder.length;
    if(len === 0) return null;
    return dfs(inorder, 0, len-1,
              postorder, 0, len-1);
}
function dfs(inorder, inStart, inEnd,
              postorder, postStart, postEnd){
    if(postStart > postEnd) {
        return null;
    }
    
    const root_val = postorder[postEnd];
    let node = new TreeNode(root_val);
    if(postStart === postEnd) return node;
    
    let left_num = 0;
    while(inorder[inStart + left_num] !== root_val) {
        left_num++;
    }
    node.left = dfs(inorder, inStart, inStart+left_num-1, 
                   postorder, postStart, postStart+left_num-1);
    node.right = dfs(inorder, inStart+left_num+1, inEnd, 
                    postorder, postStart+left_num, postEnd-1);
    return node;
}
1

弱弱的问一句啊!!!int[]数组不让出现null元素,那构造出来的树岂不是就是半满树???

C语言 一种不用函数递归的解法。
大致思路就是把原来的二叉树全部拆成左偏树,每当两个左偏树可以合成为一个子树时,就把它们变成一个子树,并在后续和其他左偏树继续合成为子树。时间复杂度和空间复杂度均为O(n)。

struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize){
    int top=0,i=0,j=0;
    struct TreeNode *stack[inorderSize],*tmp=NULL;
    while ( i<inorderSize ) {
        struct TreeNode *p=(struct TreeNode*)malloc(sizeof(struct TreeNode));
        p->left=NULL,p->right=NULL,p->val=inorder[i];;
        if ( inorder[i]==postorder[j] ) {
            if ( tmp ) p->left=tmp;
            tmp=p;
            i++,j++;
        }
        else if ( top&&postorder[j]==stack[top-1]->val ) {
            stack[--top]->right=tmp;
            tmp=stack[top];
            j++;
        } 
        else {
            stack[top++]=p;
            if ( tmp ) p->left=tmp;
            tmp=NULL;
            i++;
        }
    }
    while ( j<postorderSize ) {
        stack[--top]->right=tmp;
        tmp=stack[top];
        j++;
    }
    return tmp;
}