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

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

package 二叉树.BT;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
/**
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal/ 
 * @author Huangyujun
 */
//pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
//pre 可以用于划分出两个树,而 post 用于找根
//通过一个 map 更好的划分区间(有了位置)
public class _889_根据前序和后序遍历构造二叉树 {
    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;
        }
    }

    //~前序或后序可以放到map中,这里选择后序)
    // 定义一个 map,键值对,【值, 位置】
        int[] pre;
        int[] post;
        int preIndex = 0;
        Map<Integer, Integer> postOrderMap = new HashMap<>();
        
        public TreeNode constructFromPrePost(int[] pre, int[] post) {
            this.pre = pre;
            this.post = post;
            int index = 0;
            for (Integer val : post) 
                postOrderMap.put(val, index++);
            return helper(0, post.length - 1);
        }
        
        private TreeNode helper(int postLeft, int postRight) {
            if (postLeft > postRight || preIndex >= pre.length) 
                return null;
            TreeNode root = new TreeNode(pre[preIndex++]);
            if (preIndex == post.length || postLeft == postRight)
                return root;
            int postIndex = postOrderMap.get(pre[preIndex]);
            root.left = helper(postLeft, postIndex);
            root.right = helper(postIndex + 1, postRight - 1);
            return root;
        }
        

        /**
         * 大佬代码启发:如何使得第一个根结点判断之后,后序根结点的判断规律趋于一致:都是只要找到: 前序的根(左结点的开始)~
         * 后序的根(第二次) 大佬的代码是: 就是看透前序和后序本身,直接转化成位置{数形结合}
         * 
         * 前序 (根)【*---左子树内容(其实内部也是根左右)----】【----右子树内容----】 
         * 后序:【----左子树内容(其实内部也是左右根)---*】【----右子树内容----】(根)
         * 前序的左子树内部(也是根左右),后序的左子树(也是左右根) 前序当前的根的值A(左子树开始)~走走走~ 后序:根的值A 是相等(则是)  
         * @param pre
         * @param post
         * @return
         */
        // pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
        public TreeNode constructFromPrePost2(int[] pre, int[] post) {
            if (pre == null || pre.length == 0) {
                return null;
            }
            if (pre == null || pre.length == 0) {
                return null;
            }
            // 数组长度为1时,直接返回即可
            if (pre.length == 1) {
                return new TreeNode(pre[0]);
            }
            // 根据前序数组的第一个元素,创建根节点
            TreeNode root = new TreeNode(pre[0]);
            int n = pre.length;
            for (int i = 0; i < post.length; ++i) {
                if (pre[i + 1] == post[i]) {
                    // 根据前序数组第二个元素,确定后序数组左子树范围
                    int left_count = i + 1;
                    // 拆分前序和后序数组,分成四份
                    int[] pre_left = Arrays.copyOfRange(pre, 1, left_count + 1);
                    int[] pre_right = Arrays.copyOfRange(pre, left_count + 1, n);
                    int[] post_left = Arrays.copyOfRange(post, 0, left_count);
                    int[] post_right = Arrays.copyOfRange(post, left_count, n - 1);
                    // 递归执行前序数组左边、后序数组左边
                    root.left = constructFromPrePost(pre_left, post_left);
                    // 递归执行前序数组右边、后序数组右边
                    root.right = constructFromPrePost(pre_right, post_right);
                    break;
                }
            }
            // 返回根节点
            return root;
        }
}

本文来自博客园,作者:一乐乐,转载请注明原文链接:https://www.cnblogs.com/shan333/p/15709264.html

原文地址:https://www.cnblogs.com/shan333/p/15709264.html