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

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package 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 */