剑指offer学习（Java）——面试题7：重建二叉树

深碍√TFBOYSˉ_ 2022-05-22 10:55 179阅读 0赞

题目：输入某二叉树的前序遍历和中序遍历结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

牛客题目地址：[重建二叉树][Link 1]

/**
     * Definition for binary tree
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
        public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
            if (pre == null || in == null || pre.length == 0 || in.length == 0) {
                return null;
            }
            return ConstructCore(pre, in, 0, pre.length-1, 0, in.length-1);
        }
    
        private TreeNode ConstructCore(int[] pre, int[] in, int startPre, int endPre, int startIn, int endIn) {
            int rootVal = pre[startPre];
            TreeNode root = new TreeNode(rootVal);
            if (startPre == endPre) {
                if (startIn == endIn && startPre == startIn) {
                    return root;
                }
            }
    
            int rootIn = startIn;
            while (rootIn <= endIn && in[rootIn] != rootVal) {
                rootIn++;
            }
    
            int leftLength = rootIn - startIn;
            int leftEndPre = startPre + leftLength;
            if (leftLength > 0) {
                root.left = ConstructCore(pre, in, startPre + 1, leftEndPre, startIn, rootIn - 1);
            }
            if (leftLength < endPre - startPre) {
                root.right = ConstructCore(pre, in, leftEndPre + 1, endPre, rootIn + 1, endIn);
            }
            return root;
        }
    }

做完题会引发一些思考，这里题目中的假设“输入的前序遍历和中序遍历的结果中都不含重复的数字”，是很关键的，不然在中序遍历中就没发确定根的位置了，也就无法重建二叉树，

那么由后序+中序来重建二叉树也是类似的逻辑，代码也只需简单修改，

先序+后序 是无法重建二叉树的，比如根是1、左子节点是2 和根是1、右子节点是2的两个二叉树的遍历结果是相同的。

[Link 1]: https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=13&tqId=11157&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking