首页 > 代码库 > 二叉树 根据后序遍历生成二叉树
二叉树 根据后序遍历生成二叉树
题目：给定一个二叉树的后序遍历数组arr[]，生成二叉树
解题思路：根据搜索二叉树的性质，数组的最后一位arr[end]是二叉树的根，而且数组的左部分比arr[end]小，是根节点的左子数，数字的右部分比arr[end]大，是数组的右子数。
Example:
树的形状如上图，后序遍历为：1 3 2 6 8 7 5
arr[end] = 5;
左部分（左子树）：{1，3，2}
右部分（右子树）：{6，8，7}
package cn.edu.algorithm.prototype;/** * 根据后序遍历构造二叉树 */public class Main { public static void main(String[] args) { int[] arr = {1, 3, 2, 6, 8, 7, 5}; TreeNode root = postToBST(arr, 0, arr.length - 1); inOrder(root); } public static void inOrder(TreeNode node) { if (node != null) { inOrder(node.left); System.out.println(node.value); inOrder(node.right); } } public static TreeNode postToBST(int[] arr, int start, int end) { if (start > end) return null; TreeNode node = new TreeNode(arr[end]); int less = -1; int more = end; for (int i = start; i < end; i++) { if (arr[end] > arr[i]) { less = i; } else { more = more == end ? i : more; } } node.left = postToBST(arr, start, less); node.right = postToBST(arr, more, end - 1); return node; }}class TreeNode { protected int value; protected TreeNode left; protected TreeNode right; public TreeNode(int value) { this.value =http://www.mamicode.com/ value; }}
二叉树 根据后序遍历生成二叉树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。