[面试|算法] 三种不同组合情况，还原二叉树

前序

字节秋招一面（提前批，商业化技术，base深圳）和美团秋招（base上海），

都出现了差不多的算法题：根据数组形式的二叉树的前序序列和中序序列，假设树种没有重复元素，现要求还原该二叉树，并返回该二叉树的层次序列、后序序列。

当时手撕算法，是以牛客ACM模式，要求自己建立数据结构，传入数组，实现算法。

但只是懂的根据前序序列和中序序列来还原二叉树还是不够的，其他的组合情况也要掌握，在后文一并解决这个。

还原二叉树

4种遍历方式

先来确定二叉树的4种遍历方式：

层次序列/层次遍历：
1. 访问根节点
2. 从上到下、从左到右，一次遍历每个节点
前序序列/前序遍历：
1. 访问根节点
2. 前序遍历左子树
3. 前序遍历右子树
中序序列/中序遍历：
1. 中序遍历左子树
2. 访问根节点
3. 中序遍历右子树
后序序列/后序遍历：
1. 后序遍历左子树
2. 后序遍历右子树
3. 访问根节点

数据结构

class TreeNode

import java.util.LinkedList;
import java.util.Queue;

public class TreeNode {
    int value;
    TreeNode leftChild;
    TreeNode rightChild;

    TreeNode() {}
    TreeNode(int value) { this.value = value; }
    TreeNode(int value, TreeNode leftChild, TreeNode rightChild) {
        this.value = value;
        this.leftChild = leftChild;
        this.leftChild = rightChild;
    }

    /**
     * 层序遍历
     */
    public String readLevel() {
        Queue<TreeNode> queue = new LinkedList<>();
        StringBuilder result = new StringBuilder();
        queue.offer(this);
        while (!queue.isEmpty()) {
            TreeNode curNode = queue.poll();
            result.append(curNode.value + " ");
            if (curNode.leftChild != null) {
                queue.offer(curNode.leftChild);
            }
            if (curNode.rightChild != null) {
                queue.offer(curNode.rightChild);
            }
        }
        return result.toString();
    }

    /**
     * 前序遍历
     */
    public String readPre() {
        StringBuilder result = new StringBuilder();
        result.append(value + " "); //前序遍历
        if (leftChild != null) {
            result.append(leftChild.readPre());
        }
        if (rightChild != null) {
            result.append(rightChild.readPre());
        }
        return result.toString();
    }

    /**
     * 中序遍历
     */
    public String readMid() {
        StringBuilder result = new StringBuilder();
        if (leftChild != null) {
            result.append(leftChild.readMid());
        }
        result.append(value + " "); //中序遍历
        if (rightChild != null) {
            result.append(rightChild.readMid());
        }
        return result.toString();
    }

    /**
     * 后序遍历
     */
    public String readEnd() {
        StringBuilder result = new StringBuilder();
        if (leftChild != null) {
            result.append(leftChild.readEnd());
        }
        if (rightChild != null) {
            result.append(rightChild.readEnd());
        }
        result.append(value + " "); //后序遍历
        return result.toString();
    }

    @Override
    public boolean equals(Object parm) {
        if (parm == null || !(parm instanceof TreeNode)) {
            return false;
        }

        TreeNode obj = (TreeNode) parm;
        if (this.value == obj.value) {
        // if (this.value == obj.value || this.value.equals(obj.value)) {
            if ((this.leftChild == null && obj.leftChild == null) || this.leftChild.equals(obj.leftChild)) {
                if ((this.rightChild == null && obj.rightChild == null) || this.rightChild.equals(obj.rightChild)) {
                    return true;
                }
            }
        }
        return false;
    }
}

3种组合的算法

1. 前序序列+中序序列

reConstruct_PreMid

前序序列的第一个元素必定是根结点；
在中序序列中找根节点，确定根结点的左子树、右子树的中序序列；
在前序序列中确定根结点的左子树、右子树的前序序列；
由左子树的前序序列和中序序列建立左子树；
由右子树的前序序列和中序序列建立右子树。

/**
 * 已知 前序序列+中序序列
 * 
 * @param preOrder 前序序列
 * @param midOrder 中序序列
 * @return root 根节点
 */
public static TreeNode reConstruct_PreMid(int[] preOrder, int[] midOrder) {
    if (preOrder.length == 0 || midOrder.length == 0) {
        return null;
    }
    // preOrder[0] 必定是root根节点
    TreeNode root = new TreeNode(preOrder[0]);
    for (int i = 0; i < midOrder.length; i++) {
        if (preOrder[0] == midOrder[i]) {
            root.leftChild = reConstruct_PreMid(Arrays.copyOfRange(preOrder, 1, i + 1),
                    Arrays.copyOfRange(midOrder, 0, i));
            root.rightChild = reConstruct_PreMid(Arrays.copyOfRange(preOrder, i + 1, preOrder.length),
                    Arrays.copyOfRange(midOrder, i + 1, midOrder.length));
        }
    }
    return root;
}

2. 中序序列+后序序列

reConstruct_MidEnd

后序序列的最后一个元素必定是根结点；
在中序序列中找根节点，确定根结点的左子树、右子树的中序序列；
在后序序列中确定根结点的左子树、右子树的后序序列；
由左子树的中序序列和后序序列建立左子树；
由右子树的中序序列和后序序列建立右子树。

/**
 * 已知 中序序列+后序序列
 * 
 * @param midOrder
 * @param endOrder
 * @return root 根节点
 */
public static TreeNode reConstruct_MidEnd(int[] midOrder, int[] endOrder) {
    if (midOrder.length == 0 || endOrder.length == 0) {
        return null;
    }
    // endOrder[endOrder.length-1] 必定是root根节点
    TreeNode root = new TreeNode(endOrder[endOrder.length - 1]);
    for (int i = 0; i < midOrder.length; i++) {
        if (endOrder[endOrder.length - 1] == midOrder[i]) {
            root.leftChild = reConstruct_MidEnd(Arrays.copyOfRange(midOrder, 0, i),
                    Arrays.copyOfRange(endOrder, 0, i));
            root.rightChild = reConstruct_MidEnd(Arrays.copyOfRange(midOrder, i + 1, midOrder.length),
                    Arrays.copyOfRange(endOrder, i, endOrder.length - 1));
        }
    }
    return root;
}

3. 层序序列+中序序列

这种组合情况比较复杂，需要考虑节点所在的层数，相对应的算法也比较复杂，下面的算法是参考了GitHub上看到的。

buildTreeByMidLevel

层序序列的第一个元素必定是根结点；
根据根节点在中序序列中，划分左子树的中序序列、右子树的中序序列；
在层序序列中获取其左子树、右子树的层序序列；
由左子树的层序序列和中序序列建立左子树；
由右子树的层序序列和中序序列建立右子树。

/**
 * 已知 层序序列+中序序列
 * 
 * @param levelOrder
 * @param midOrder
 * @param midBegin   中序序列的起始位置
 * @param midEnd     中序序列的中止位置
 * @return root 根节点
 */
public static TreeNode buildTreeByMidLevel(int[] levelOrder, int[] midOrder, int midBegin, int midEnd) {
    if (levelOrder.length == 0 || midOrder.length == 0) {
        return null;
    }
    // levelOrder[0] 必定是root根节点
    TreeNode root = new TreeNode(levelOrder[0]);
    // rootLocation：（子）序列中根节点的位置
    int rootLocation = -1;
    for (int i = midBegin; i <= midEnd; i++) {
        if (midOrder[i] == levelOrder[0]) {
            rootLocation = i;
            break;
        }
    }
    // 划分左右子树
    // levelOrder.length会影响划分
    if (levelOrder.length >= 2) {
        if (isLeft(midOrder, levelOrder[0], levelOrder[1])) {
            // 左子树
            root.leftChild = buildTreeByMidLevel(getLevelStr(midOrder, midBegin, rootLocation - 1, levelOrder),
                    midOrder, midBegin, rootLocation - 1);
            // 处理左子树为空的情况,注意levelOrder.length需>=3
            if (levelOrder.length >= 3 && !isLeft(midOrder, levelOrder[0], levelOrder[2])) {
                root.rightChild = buildTreeByMidLevel(getLevelStr(midOrder, rootLocation + 1, midEnd, levelOrder),
                        midOrder, rootLocation + 1, midEnd);
            }
        } else {
            // 右子树
            root.rightChild = buildTreeByMidLevel(getLevelStr(midOrder, rootLocation + 1, midEnd, levelOrder),
                    midOrder, rootLocation + 1, midEnd);
        }
    }
    return root;
}
/**
 * 区分左右子树
 * 在中序序列[]中,若孩子节点在根节点左边，则返回true，否则返回false
 * 
 * @param order
 * @param root
 * @param child
 * @return isLeft/isRight
*/
public static boolean isLeft(int[] order, int root, int child) {
    boolean findVal = false;
    for (int temp : order) {
        if (temp == child) {
            findVal = true;
        } else if (temp == root) {
            return findVal;
        }
    }
    return false;
}
/**
 * 获取左右子树各自在层序序列中的子序列
 * 将中序序列中midBegin与MidEnd之间的节点依次从levelOrder中提取出来，保持levelOrder中的字符顺序不变
 * 比如，右子树的中序序列[15,20,7]在层序序列中是[20,15,7]
 * 
 * @param midOrder
 * @param midBegin
 * @param midEnd
 * @param levelOrder
 * @return result[] 子树在层序序列中的子序列
*/
public static int[] getLevelStr(int[] midOrder, int midBegin, int midEnd, int[] levelOrder) {
    int[] result = new int[midEnd - midBegin + 1];
    int curLoc = 0;
    for (int i = 0; i < levelOrder.length; i++) {
        if (contains(midOrder, levelOrder[i], midBegin, midEnd)) {
            result[curLoc++] = levelOrder[i];
        }
    }
    return result;
}
/**
 * 判断层序序列中的节点是否在中序序列中
 * 在中序序列[]中的begin和end位置之间（包括begin和end）含有字符target,则返回true
 * 
 * @param midOrder
 * @param target
 * @param midBegin
 * @param midEnd
 * @return false/true
*/
public static boolean contains(int[] midOrder, int target, int midBegin, int midEnd) {
    for (int i = midBegin; i <= midEnd; i++) {
        if (midOrder[i] == target) {
            return true;
        }
    }
    return false;
}

其他情况

其他的遍历组合均不能还原出二叉树的形状，因为无法确认其左右孩子。

例如：前序序列+后序序列，前序序列和后序序列在本质上都是将父节点与子结点进行分离，但并没有指明左子树和右子树的能力，因此这两个序列只能明确根节点、父子关系，而不能确定一个二叉树。

参考资料

Java数据结构与算法——二叉树及操作(包括二叉树遍历)

Java一维数组转换二叉树结构

GitHub

完整代码

import java.util.Arrays;

/**
 * Solution
 */
public class Solution {

    public static void main(String[] args) {
        int[] levelOrder = new int[] { 3, 9, 20, 15, 7 };
        int[] preOrder = new int[] { 3, 9, 20, 15, 7 };
        int[] midOrder = new int[] { 9, 3, 15, 20, 7 };
        int[] endOrder = new int[] { 9, 15, 7, 20, 3 };


        System.out.println("==已知前序序列+中序序列==");
        System.out.println("层序遍历: " + reConstruct_PreMid(preOrder, midOrder).readLevel());
        // System.out.println("前序遍历: " + reConstruct_PreMid(preOrder, midOrder).readPre());
        // System.out.println("中序遍历: " + reConstruct_PreMid(preOrder, midOrder).readMid());
        System.out.println("后序遍历: " + reConstruct_PreMid(preOrder, midOrder).readEnd());
        System.out.println();

        System.out.println("==已知中序序列+后序序列==");
        System.out.println("层序遍历: " + reConstruct_MidEnd(midOrder, endOrder).readLevel());
        System.out.println("前序遍历: " + reConstruct_MidEnd(midOrder, endOrder).readPre());
        // System.out.println("中序遍历: " + reConstruct_MidEnd(midOrder, endOrder).readMid());
        // System.out.println("后序遍历: " + reConstruct_MidEnd(midOrder, endOrder).readEnd());
        System.out.println();

        System.out.println("==已知层序序列+中序序列==");
        // System.out.println("层序遍历: " + buildTreeByMidLevel(levelOrder, midOrder, 0, midOrder.length-1).readLevel());
        System.out.println("前序遍历: " + buildTreeByMidLevel(levelOrder, midOrder, 0, midOrder.length-1).readPre());
        // System.out.println("中序遍历: " + buildTreeByMidLevel(levelOrder, midOrder, 0, midOrder.length-1).readMid());
        System.out.println("后序遍历: " + buildTreeByMidLevel(levelOrder, midOrder, 0, midOrder.length-1).readEnd());
        System.out.println();
    }

    /**
     * 已知 前序序列+中序序列
     * 
     * @param preOrder 前序序列
     * @param midOrder 中序序列
     * @return root 根节点
     */
    public static TreeNode reConstruct_PreMid(int[] preOrder, int[] midOrder) {
        if (preOrder.length == 0 || midOrder.length == 0) {
            return null;
        }
        // preOrder[0] 必定是root根节点
        TreeNode root = new TreeNode(preOrder[0]);
        for (int i = 0; i < midOrder.length; i++) {
            if (preOrder[0] == midOrder[i]) {
                root.leftChild = reConstruct_PreMid(Arrays.copyOfRange(preOrder, 1, i + 1),
                        Arrays.copyOfRange(midOrder, 0, i));
                root.rightChild = reConstruct_PreMid(Arrays.copyOfRange(preOrder, i + 1, preOrder.length),
                        Arrays.copyOfRange(midOrder, i + 1, midOrder.length));
            }
        }
        return root;
    }

    /**
     * 已知 中序序列+后序序列
     * 
     * @param midOrder
     * @param endOrder
     * @return root 根节点
     */
    public static TreeNode reConstruct_MidEnd(int[] midOrder, int[] endOrder) {
        if (midOrder.length == 0 || endOrder.length == 0) {
            return null;
        }
        // endOrder[endOrder.length-1] 必定是root根节点
        TreeNode root = new TreeNode(endOrder[endOrder.length - 1]);
        for (int i = 0; i < midOrder.length; i++) {
            if (endOrder[endOrder.length - 1] == midOrder[i]) {
                root.leftChild = reConstruct_MidEnd(Arrays.copyOfRange(midOrder, 0, i),
                        Arrays.copyOfRange(endOrder, 0, i));
                root.rightChild = reConstruct_MidEnd(Arrays.copyOfRange(midOrder, i + 1, midOrder.length),
                        Arrays.copyOfRange(endOrder, i, endOrder.length - 1));
            }
        }
        return root;
    }

    /**
     * 已知 层序序列+中序序列
     * 
     * @param levelOrder
     * @param midOrder
     * @param midBegin   中序序列的起始位置
     * @param midEnd     中序序列的中止位置
     * @return root 根节点
     */
    public static TreeNode buildTreeByMidLevel(int[] levelOrder, int[] midOrder, int midBegin, int midEnd) {
        if (levelOrder.length == 0 || midOrder.length == 0) {
            return null;
        }

        // levelOrder[0] 必定是root根节点
        TreeNode root = new TreeNode(levelOrder[0]);

        // rootLocation：（子）序列中根节点的位置
        int rootLocation = -1;
        for (int i = midBegin; i <= midEnd; i++) {
            if (midOrder[i] == levelOrder[0]) {
                rootLocation = i;
                break;
            }
        }

        // 划分左右子树
        // levelOrder.length会影响划分
        if (levelOrder.length >= 2) {
            if (isLeft(midOrder, levelOrder[0], levelOrder[1])) {
                // 左子树
                root.leftChild = buildTreeByMidLevel(getLevelStr(midOrder, midBegin, rootLocation - 1, levelOrder),
                        midOrder, midBegin, rootLocation - 1);
                // 处理左子树为空的情况,注意levelOrder.length需>=3
                if (levelOrder.length >= 3 && !isLeft(midOrder, levelOrder[0], levelOrder[2])) {
                    root.rightChild = buildTreeByMidLevel(getLevelStr(midOrder, rootLocation + 1, midEnd, levelOrder),
                            midOrder, rootLocation + 1, midEnd);
                }
            } else {
                // 右子树
                root.rightChild = buildTreeByMidLevel(getLevelStr(midOrder, rootLocation + 1, midEnd, levelOrder),
                        midOrder, rootLocation + 1, midEnd);
            }
        }
        return root;
    }

    /**
     * 区分左右子树
     * 在中序序列[]中,若孩子节点在根节点左边，则返回true，否则返回false
     * 
     * @param order
     * @param root
     * @param child
     * @return isLeft/isRight
    */
    public static boolean isLeft(int[] order, int root, int child) {
        boolean findVal = false;
        for (int temp : order) {
            if (temp == child) {
                findVal = true;
            } else if (temp == root) {
                return findVal;
            }
        }
        return false;
    }

    /**
     * 获取左右子树各自在层序序列中的子序列
     * 将中序序列中midBegin与MidEnd之间的节点依次从levelOrder中提取出来，保持levelOrder中的字符顺序不变
     * 比如，右子树的中序序列[15,20,7]在层序序列中是[20,15,7]
     * 
     * @param midOrder
     * @param midBegin
     * @param midEnd
     * @param levelOrder
     * @return result[] 子树在层序序列中的子序列
    */
    public static int[] getLevelStr(int[] midOrder, int midBegin, int midEnd, int[] levelOrder) {
        int[] result = new int[midEnd - midBegin + 1];
        int curLoc = 0;
        for (int i = 0; i < levelOrder.length; i++) {
            if (contains(midOrder, levelOrder[i], midBegin, midEnd)) {
                result[curLoc++] = levelOrder[i];
            }
        }
        return result;
    }

    /**
     * 判断层序序列中的节点是否在中序序列中
     * 在中序序列[]中的begin和end位置之间（包括begin和end）含有字符target,则返回true
     * 
     * @param midOrder
     * @param target
     * @param midBegin
     * @param midEnd
     * @return false/true
    */
    public static boolean contains(int[] midOrder, int target, int midBegin, int midEnd) {
        for (int i = midBegin; i <= midEnd; i++) {
            if (midOrder[i] == target) {
                return true;
            }
        }
        return false;
    }
}

#字节跳动秋招提前批##学习路径##Java#