剑指offer学习(Java)——面试题7:重建二叉树 深碍√TFBOYSˉ_ 2022-05-22 10:55 137阅读 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
还没有评论,来说两句吧...