前序、中序、后序遍历之二构造二叉树

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

思路：
  1. 定义一个Map保存中序遍历时每一个元素及对应的索引方便快速定位；
  2. 因为构造二叉树，所以需要先找到根节点，前序中左右，后序左右中，因此它们的根节点好找，由于没有前序，按照后序寻找根节点；
     前序遍历：[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
     中序遍历：[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
     后序遍历：[ [左子树的前序遍历结果], [右子树的前序遍历结果], 根节点 ]
  3. 然后构建一个二叉树新的节点；
  4. 之后找到在中序遍历中的根节点，由于之前定义了Map，可以根据后序遍历最后一个节点作为键寻找value，即对应的中序遍历过程中对应值的索引；
  5. 后续通过当前根节点索引减去[左子树的中序遍历结果]中最左元素索引得到左子树数；
  6. 递归构建对应的子节点：
     中序按照当前根节点截断，因此不取当前根节点，分别为[左子树的中序遍历结果]最左索引到当前根节点索引减一，当前根节点索引加一到[右子树的中序遍历结果]最右索引；
     后序在最后一个节点截断，因此不取最后一个节点，本身计算了左子树的元素数，对应索引范围就分别为[左子树的前序遍历结果]最左索引到[左子树的前序遍历结果]最左索引加左子树元素数减一，[左子树的前序遍历结果]最左索引加左子树元素数到[右子树的前序遍历结果]最右节点索引。

ps：构造方法与this相关知识点。

/**
 * 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 {
    private Map<Integer,Integer> indexMap;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = postorder.length;
        indexMap = new HashMap<>();
        for(int i = 0;i < inorder.length;i++){
            indexMap.put(inorder[i],i);
        }
        return myBuildTree(inorder,postorder,0,n-1,0,n-1);
    }

    public TreeNode myBuildTree(int[] inorder, int[] postorder,int inorder_left,int inorder_right,int postorder_left,int postorder_right){
        if(postorder_left > postorder_right){
            return null;
        }
        //根据后序遍历获取左右中的中在中序的位置
        int inorder_root = indexMap.get(postorder[postorder_right]);
        //构建节点
        TreeNode root = new TreeNode(postorder[postorder_right]);
        //计算两种模式下根节点差
        int size_left_subtree = inorder_root - inorder_left;
        //切割中序遍历与后序遍历的root节点
        root.left = myBuildTree(inorder, postorder, inorder_left, inorder_root - 1, postorder_left, postorder_left + size_left_subtree - 1);
        root.right = myBuildTree(inorder, postorder, inorder_root + 1, inorder_right, postorder_left + size_left_subtree, postorder_right - 1);
        return root;
    }
}

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

思路：
  1. 定义一个Map保存中序遍历时每一个元素及对应的索引方便快速定位；
  2. 因为构造二叉树，所以需要先找到根节点，前序中左右，后序左右中，因此它们的根节点好找，由于没有后序，按照前序寻找根节点；
     前序遍历：[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
     中序遍历：[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
     后序遍历：[ [左子树的前序遍历结果], [右子树的前序遍历结果], 根节点 ]
  3. 然后构建一个二叉树新的节点；
  4. 之后找到在中序遍历中的根节点，由于之前定义了Map，可以根据前序遍历第一个节点作为键寻找value，即对应的中序遍历过程中对应值的索引；
  5. 后续通过当前根节点索引减去[左子树的中序遍历结果]中最左元素索引得到左子树数；
  6. 递归构建对应的子节点：
     中序按照当前根节点截断，因此不取当前根节点，分别为[左子树的中序遍历结果]最左索引到当前根节点索引减一，当前根节点索引加一到[右子树的中序遍历结果]最右索引；
     前序在第一个节点截断，因此不取第一个节点，本身计算了左子树的元素数，对应索引范围就分别为[左子树的后序遍历结果]最左索引加一到[左子树的后序遍历结果]最左索引加左子树元素数，[左子树的后序遍历结果]最左索引加左子树元素数加一到[右子树的后序遍历结果]最右节点索引。
/**
 * 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 {
    private Map<Integer,Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        map = new HashMap<Integer,Integer>();
        for(int i = 0;i < inorder.length;i++){
            map.put(inorder[i],i);
        }
        return getRes(preorder,inorder,0,n-1,0,n-1);
    }

    private TreeNode getRes(int[] preorder, int[] inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right){
        if(preorder_left > preorder_right){
            return null;
        }

        int inorder_root = map.get(preorder[preorder_left]);
        TreeNode node = new TreeNode(preorder[preorder_left]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
         // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        //构造前序遍历：[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
        //构造中序遍历：[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
        node.left = getRes(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        node.right = getRes(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return node;
    }
}

根据前序和后序遍历构造二叉树

思路：
  1. 定义一个Map保存后序遍历时每一个元素及对应的索引方便快速定位；
  2. 因为构造二叉树，所以需要先找到根节点，前序中左右，后序左右中，因此它们的根节点好找，寻找根节点；
     前序遍历：[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
     中序遍历：[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
     后序遍历：[ [左子树的前序遍历结果], [右子树的前序遍历结果], 根节点 ]
  3. 然后构建一个二叉树新的节点；
  4. 之后找到在后序遍历中的根节点，由于之前定义了Map，可以根据前序遍历第一个节点作为键寻找value，即对应的后序遍历过程中对应值的索引；
  5. if (preorder_left == preorder_right)：如果前序遍历数组的左边界等于右边界，说明当前子树只有一个节点，直接返回该节点；
     在另外两种构建二叉树的过程中，当递归到只剩下一个节点时，在计算左右子树节点数量和划分左右子树区间时，会自然地使得子树的左右边界出现preLeft > preRight的情况，从而触发已有的终止条件；
     仅根据前序和后序遍历无法唯一确定左右子树的划分。
  6. 获取左子树的根节点在前序遍历中的索引，之后通过Map获取左子树的根节点在后序遍历中的索引；
  7. 左子树的大小等于左子树的根节点在后序遍历数组中的位置减去后序遍历数组的左边界再加1；
     [ [[左子树左子树的前序遍历结果],[左子树右子树的前序遍历结果],左子树根节点], [右子树的前序遍历结果], 根节点 ]
  8. 递归构建对应的子节点：
     如果左子树的根节点在后序遍历数组中的位置加1小于等于后序遍历数组的右边界，说明存在右子树；
     递归调用 build 方法构建右子树，更新前序遍历和后序遍历数组的左右边界。
/**
 * 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 {
    private Map<Integer, Integer> indexMap;
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        int n = postorder.length;
        indexMap = new HashMap<Integer,Integer>();
        for(int i = 0;i < postorder.length;i++){
            indexMap.put(postorder[i],i);
        }
        return build(preorder,postorder,0,n-1,0,n-1);
    }

    public TreeNode build(int[] preorder, int[] postorder,int preorder_left,int preorder_right,int postorder_left,int postorder_right){
        if (preorder_left > preorder_right) {
            return null;
        }

        int postorder_root = indexMap.get(preorder[preorder_left]);
        TreeNode root = new TreeNode(preorder[preorder_left]);

        if (preorder_left == preorder_right) { // 只有一个节点
            return root;
        }

        int preorder_left_child = preorder_left + 1; // 左子树的根节点在前序遍历中的索引
        int postorder_left_child = indexMap.get(preorder[preorder_left_child]); // 左子树的根节点在后序遍历中的索引

        int left_subtree_size = postorder_left_child - postorder_left + 1; // 左子树的大小

        // 构建左子树
        root.left = build(preorder, postorder, preorder_left + 1, preorder_left + left_subtree_size, postorder_left, postorder_left + left_subtree_size - 1);

        // 构建右子树
        if (postorder_left_child + 1 <= postorder_right) {
            root.right = build(preorder, postorder, preorder_left + left_subtree_size + 1, preorder_right, postorder_left_child + 1, postorder_right - 1);
        }

        return root;
    }

}
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容