【简单】根据后序数组重建搜索二叉树－Java：进阶问题

分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.BinaryTree; import live.every.day.ProgrammingDesign.CodingInterviewGuide.BinaryTree.BinaryTreePrinter2.Node; import static live.every.day.ProgrammingDesign.CodingInterviewGuide.BinaryTree.BinaryTreePrinter2.print; /** * 根据后序数组重建搜索二叉树 * * 【题目】 * 进阶如果整型数组arr中没有重复值且已知是一棵搜索二叉树的后序遍历结果通过数组arr重构二叉树。 * * 【难度】 * 简单 * * 【解答】 * 进阶问题的分析与原问题同理一棵树的后序数组中最后一个值为二叉树头节点的值数组左部分都比头节点的值小用来生成头节点 * 的左子树剩下的部分用来生成右子树。 * 具体过程请参看如下代码中的postArrayToBST方法。 * * author Created by LiveEveryDay */ public class ReconstructBSTByPostArray2 { public static Node postArrayToBST(int[] arr) { if (arr null) { return null; } return postToBST(arr, 0, arr.length - 1); } private static Node postToBST(int[] arr, int start, int end) { if (start end) { return null; } Node root new Node(arr[end]); int less -1; int greater end; for (int i start; i end; i) { if (arr[end] arr[i]) { less i; } else { greater greater end ? i : greater; } } root.left postToBST(arr, start, less); root.right postToBST(arr, greater, end - 1); return root; } public static void main(String[] args) { int[] a {2, 1, 3, 6, 5, 7, 4}; Node root postArrayToBST(a); print(root); } } // ------ Output ------ /* 4 / \ 3 7 / / 1 5 \ \ 2 6 */