leetcode-106 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.

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

根据中序和后续得出结果：

具体实现方法找出首先在后续中找出“根节点”，然后找出中序的这个根节点所在位置将中序分为左右两个节点，在将左节点中的数据在后续中找到对应的跟，右节点也在后续中找到对应的根节点依次循环，直到找出所有节点

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder== null || inorder == null || postorder.length == 0) {
            return null;
        }else if(postorder.length != inorder.length){
            return null;
        }
        return buildTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
        
    }
    
    public TreeNode buildTree(int[] inorder,int is,int ie, int[] postorder,int ps,int pe) {
        if(is>ie || ps>pe || is<0 || ps<0) {
            return null;
        }
        TreeNode begin = new TreeNode(postorder[pe]);
        if(is ==ie && ps == pe ) {
            return begin;
        }
        
        
        //找出中序中节点所在的位置 分为左右两边节点
        //小于tmpIe的为左节点，大于的为右节点
        int tmpIe = -1;
        for(int index=is;index<=ie;index++) {
            if(inorder[index] == postorder[pe]) {
                tmpIe = index;
                break;
            }
        }
        
        
        int endPe = ps+tmpIe-is-1;
        begin.left=buildTree(inorder,is,tmpIe-1,postorder,ps,endPe);
        begin.right = buildTree(inorder,tmpIe+1,ie,postorder,endPe+1,pe-1);
        return begin;
    }

代码可能不是很好理解，可以参照百度经验的中序后续得出结果：

1. • 

   • 从后序遍历知道，最后一个必然是根节点，因此A是根。再结合中序遍历可知HDMIBJNE是A的左子树部分，FKCG是右子树部分。

     

   • 取A的右子树部分来看先，右子树部分的中序遍历：FKCE，后序遍历：KFGC。接着从后序遍历中看A的右子树部分KFGC，所以C是根。又从中序遍历知，FK是C的左子树部分，G是C右子树。如图所示

     

   • 使用同样的方法，C的左子树部分，中序：FK，后序：KF。可以得出F是根，那么K只能是F的右子树了。此时如图所示，A的右子树部分都出来了

     

   • 再看，A的左子树部分HDMIBJE，中序：HDMIBJNE，后序：HMIDNJEB。后序遍历可知，B是根结点，那么再结合中序遍历可知道HDMI是B的左子树部分，JNE是B的右子树部分。

     

   • 紧接着就是看B的左子树部分HDMI，中序：HDMI，后序：HMID，可知D是根，H是D的左子树，MI是D的右子树部分，如图所示。

     

   • 看到D的右子树部分，中序后序都是MI，根据后序中序的特性可知道，根只能是I，M是I的左子树。

     

   • 再接着看看B的右子树部分JNE，中序：JNE，后序：NJE，后序看出E是根，中序看出E无右子树，只有JN是E的左子树部分。

     

   •  

     最后看JN的中序：JN，后序：NJ，根据后序特性看出，J是根，中序看出N是J的右子树。那么整体的二叉树就出来了，如图所示。