LeetCode 105.从前序与中序遍历序列构造二叉树 ＆＆ 106.从中序与后序遍历序列构造二叉树

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

代码实现：

import java.util.HashMap;
import java.util.Map;

/** * @Author Mr.Lu * @Date 2022/7/27 11:36 * @ClassName InorderAndPostOrderBuildTreeTest * @Version 1.0 */
public class InorderAndPreOrderBuildTreeTest {
    
    Map<Integer, Integer> map; // 方便根据数值查找位置
    public TreeNode buildTree(int[] preorder, int[] inorder){
    
        map = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
      // 用map保存中序序列的数值对应位置
            map.put(inorder[i], i);
        }
        return findNode(inorder, 0, inorder.length, preorder, 0, preorder.length);  // 前闭后开
    }

    private TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] preorder, int preBegin, int preEnd) {
    
        // 参数里的范围都是前闭后开
        if(preBegin >= preEnd || inBegin >= inEnd){
      // 不满足左闭右开，说明没有元素，返回空树
            return null;
        }

        int rootIndex = map.get(preorder[preBegin]); // 找到前序遍历的第一个元素在中序遍历的位置
        TreeNode root = new TreeNode(inorder[rootIndex]);  // 构造节点
        int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定前序数列的个数

        root.left = findNode(inorder, inBegin, rootIndex, preorder, preBegin + 1, preBegin + lenOfLeft + 1);  // 递归处理中序遍历和前序遍历的左边数组
        root.right = findNode(inorder, rootIndex + 1, inEnd, preorder, preBegin + lenOfLeft + 1, preEnd);  // 递归处理中序遍历和前序遍历的右面数组

        return root;
    }
}

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

代码实现：

import java.util.HashMap;
import java.util.Map;

/** * @Author Mr.Lu * @Date 2022/7/27 11:36 * @ClassName InorderAndPostOrderBuildTreeTest * @Version 1.0 */
public class InorderAndPostOrderBuildTreeTest {
    
    Map<Integer, Integer> map;  // 方便根据数值查找位置
    public TreeNode buildTree(int[] inorder, int[] postorder){
    
        map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++){
    
            map.put(inorder[i], i);
        }
        
        return findNode(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }

    private TreeNode findNode(int[] inorder, int inBegin, int inEnd, int[] postorder, int postBegin, int postEnd) {
    
        // 参数里的范围都是前闭后开
        if(inBegin >= inEnd || postBegin >= postEnd){
      // 不满足左闭右开，说明没有元素，直接返回
            return null;
        }

        int rootIndex = map.get(postorder[postEnd - 1]); // 找到后续遍历的最后一个元素在中序遍历中的位置
        TreeNode root = new TreeNode(inorder[rootIndex]); // 构造节点

        int lenOfLeft = rootIndex - inBegin; // 保存中序左子树个数，用来确定后续数列的个数
        root.left = findNode(inorder, inBegin, rootIndex, postorder, postBegin, postBegin + lenOfLeft);
        root.right = findNode(inorder,rootIndex + 1, inEnd, postorder, postBegin + lenOfLeft, postEnd - 1);

        return root;
    }
}

参考：代码随想录https://programmercarl.com/0106.%E4%BB%8E%E4%B8%AD%E5%BA%8F%E4%B8%8E%E5%90%8E%E5%BA%8F%E9%81%8D%E5%8E%86%E5%BA%8F%E5%88%97%E6%9E%84%E9%80%A0%E4%BA%8C%E5%8F%89%E6%A0%91.html#java