【算法】从中序与后序遍历序列构造二叉树106

描述

106. 从中序与后序遍历序列构造二叉树 - 力扣（Leetcode）

105. 从前序与中序遍历序列构造二叉树 - 力扣（Leetcode）

分析

这里的构造用确认来说更加贴切。

其实就是给你一棵树的两种遍历结果，让你判断能不能恢复树原来的样子。

这种确认有两种方式：

1. 前序 + 中序确认
2. 后序 + 中序确认

确认就是验证。

注意：必须有中序，光前序 + 后序是做不了这件事的。

实现

import java.util.Map;
import java.util.HashMap;
import java.util.Queue;
import java.util.LinkedList;

//106. 从中序与后序遍历序列构造二叉树
public class ConstructBinaryTreeFromInorderAndPostorderTraversal106 {
	public static void main(String[] args){
		TreeNode root = new Solution1().buildTree(new int[]{3,9,20,15,7}, new int[]{9,3,15,20,7});
		MyUtils.levelOrder(root);
	}
}
//中序 + 后序
class Solution {
    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);
    }

	//左闭右开
    TreeNode findNode(int[] inorder, int inStrat, int inEnd, int[] postorder, int postStart, int postEnd){
    	if (inStrat >= inEnd || postStart >= postEnd) {
    		return null;
    	}
    	
    	//拿到root在中序中的位置
    	int rootIndex = map.get(postorder[postEnd - 1]);
    	TreeNode root = new TreeNode(inorder[rootIndex]);

    	//中序数组左子树的长度
    	int lengthOfLeft = rootIndex - inStrat;
    	root.left = findNode(inorder, inStrat, rootIndex, postorder, postStart, postStart + lengthOfLeft);
    	root.right = findNode(inorder, rootIndex + 1, inEnd, postorder, postStart + lengthOfLeft, postEnd - 1);
    	return root;
    }
}
//前序 + 中序
class Solution1 {
    Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
    	map = new HashMap<>();
    	//inorder入HashMap
    	for (int i = 0; i < inorder.length; i++) {
    		map.put(inorder[i], i);
    	}
    	//因为前闭右开，所以这里不用 - 1
    	return findNode(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }
    private TreeNode findNode(
    	int[] preorder, int preStart, int preEnd,
    	int[] inorder, int inStart, int inEnd) {
    	
    	if (preStart >= preEnd || inStart >= inEnd) {
    		return null;
    	}
    	
    	TreeNode root = new TreeNode(preorder[preStart]);

    	int index = map.get(preorder[preStart]);
    	int lengthOfLeft = index - inStart;

    	root.left = findNode(preorder, preStart + 1, preStart + lengthOfLeft + 1, inorder, inStart, index);
    	root.right = findNode(preorder, preStart + lengthOfLeft + 1, preEnd, inorder, index + 1, inEnd);

    	return root;
    }
}

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	public TreeNode(){};
	public TreeNode(int val){this.val = val;}
	public TreeNode(int val, TreeNode left, TreeNode right){
		this.val = val;
		this.left = left;
		this.right = right;
	}
}

class MyUtils {
	/**
	 *二叉树的构建
	 * int[] -> 二叉树
	 */
	public static TreeNode buildTree(Integer[] arr) {
        return buildTreeHelper(arr, 0);
    }

    public static TreeNode buildTreeHelper(Integer[] arr, Integer index) {
        if (index >= arr.length || arr[index] == null) {
            return null;
        }

        TreeNode node = new TreeNode(arr[index]);

        node.left = buildTreeHelper(arr, 2 * index + 1);
        node.right = buildTreeHelper(arr, 2 * index + 2);

        return node;
    }


    public static void levelOrder(TreeNode root) {
        if (root == null) return;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            
            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();
                System.out.print(node.val + " ");
                
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            
            System.out.println();
        }
    }
}

总结