【算法】中序与后序遍历序列构造二叉树（二叉树、递归）

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

根据一棵树的中序遍历与后序遍历构造二叉树。注意:你可以假设树中没有重复的元素。例如，给出中序遍历 inorder = [9,3,15,20,7]，后序遍历 postorder = [9,15,7,20,3]返回如下的二叉树：

     3
    / \
    9 20
      / \
     15   7

 class Solution {
     public TreeNode buildTree(int[] inorder, int[] postorder) {
         return traversal(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }
   
     public TreeNode traversal(int[] inorder, int inLeft, int inRight, int[] postorder,  intpoLeft, int poRight){
         // 上来先判断是否是空树
         if(poRight - poLeft == 0)//此处必须使用Right-Left，而不是inorder.length！length始终没变，会死循环。
             return null;
         // 找到新的中间节点
         int rootValue = postorder[poRight - 1];
         TreeNode root = new TreeNode(rootValue);
         // 如果只有一个直接返回当前节点，无需后续找切点和切割
         if(poRight - poLeft == 1)//必须Right-Left
             return root;
         // 找中序遍历的切点
         int divisionPoint = inLeft;
         for(int i = inLeft; i < inRight; i++){
             if(inorder[i] == rootValue){
                 divisionPoint = i;
                 break;
            }
        }
         // root.left = traversal(inorder, inLeft, divisionPoint, postorder, poLeft, divisionPoint/*不可直接使用divisionPoint，后续的分割不取决于divisionPoint，而是中序的子串长度，因而使用加和的形式poLeft + (divisionPoint - inLeft) */);//左中，左后
         // root.right = traversal(inorder, divisionPoint + 1, inRight, postorder, divisionPoint, poRight - 1);
         root.left = traversal(inorder, inLeft, divisionPoint, postorder, poLeft/*不可使用inLeft ，为什么：从图中可以看出，分过一次之后的右子树的中序与后续的左起始index已经不再一致了*/, poLeft +(divisionPoint - inLeft));//左中，左后
         root.right = traversal(inorder, divisionPoint + 1, inRight, postorder, poLeft +(divisionPoint - inLeft), poRight - 1);
         return root;
    }
 }

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

 class Solution {
     public TreeNode buildTree(int[] preorder, int[] inorder) {
         return traversal(inorder, 0, inorder.length, preorder, 0, inorder.length);
    }
     
     public TreeNode traversal(int[] inorder, int inLeft, int inRight, int[] preorder, intpreLeft, int preRight){
         // 先判断是否为空（有两种为空的情况(错，只有一种情况，没有节点的空子节点这种情况)），为空说明为则无需后续新建节点,以及分割
         if(inRight - inLeft == 0)
             return null;
         // 有节点则直接从前序取节点即可（不要犹豫^_^）
         int rootValue = preorder[preLeft];
         TreeNode root = new TreeNode(rootValue);
 ​
         if(inRight - inLeft == 1)
             return root;
 //寻找中间节点
         int rootindex = inLeft;
         for(int i = inLeft; i < inRight; i++){
             if(inorder[i] == rootValue){
                 rootindex = i;
                 break;
            }
        }
 //分割
         root.left = traversal(inorder, inLeft, rootindex, preorder, preLeft + 1, (rootindex- inLeft) + preLeft + 1);
         root.right = traversal(inorder, rootindex + 1, inRight, preorder, (rootindex -inLeft) + preLeft + 1, preRight);
         return root;
    }
 }