[数据结构与算法]leecode 106. 从中序与后序遍历序列构造二叉树

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

递归的还原过程：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

递归：

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return buildTree1(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode buildTree1(int[] inorder, int inleft, int inright,int[] postorder, int postleft,int postright) {
//如果数组的长度<1，说明数组中无节点，返回空节点。
        if (inright - inleft < 1 || postright - postleft < 1) return null;
//如果数组长度=1，说明数组中剩一个节点，直接返回该节点，该节点值为inorder[inleft]
//这里节点值也是postorder[postleft]，因为后序遍历和中序遍历的数组长度是相同的，
//中序遍历是一个，那后序遍历也是.
        if (inright - inleft == 1) return new TreeNode(inorder[inleft]);
//记录后序遍历最后一个节点的值，这是当前的根节点的值
        int rootVal = postorder[postright-1];
//将该节点作为根节点
        TreeNode root = new TreeNode(rootVal);
        int index = 0;
//对中序数组遍历，找到和根节点相等的值作为切分点，index记录切分点
        for (int i = inleft; i < inright; i ++) {
            if (inorder[i] == rootVal) {
                index = i;
//找到之后就结束遍历
                break;
            }
        }
//递归找根节点的左节点，其中中序数组为从inleft到index部分，
//后序数组为postleft到与中序数组相同的位置，因为都是遍历，数组长度相同，
//那么左右子树只是遍历顺序不同，但是存值是相同的
        root.left = buildTree1(inorder, inleft, index,postorder, postleft, postleft + (index - inleft));
        root.right = buildTree1(inorder, index + 1, inright, postorder, postleft + (index - inleft), postright - 1);
        return root;
    }
}

?