欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

106.Construct Binary Tree from Inorder and Postorder Traversal

程序员文章站 2022-03-07 23:50:19
...

题目描述(中等难度)

106.Construct Binary Tree from Inorder and Postorder Traversal

思路分析

可以先看一下 105 题,直接在 105 题的基础上改了,大家也可以先根据 105 题改一改。

105 题给的是先序遍历和中序遍历,这里把先序遍历换成了后序遍历。

区别在于先序遍历的顺序是 根节点 -> 左子树 -> 右子树。

后序遍历的顺序是 左子树 -> 右子树 -> 根节点。

我们当然还是先确定根节点,然后在中序遍历中找根节点的位置,然后分出左子树和右子树。

对于之前的解法一,传数组的两个边界,影响不大,只要重新计算边界就可以了。

解法一

常规解法,利用递归,传递左子树和右子树的数组范围即可。

import java.util.HashMap;

class TreeNode{
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x){val=x;}
}

public class Construct_Binary_Tree_from_Inorder_and_Postorder_Traversal {
	
	public static TreeNode buildTree(int[]inorder,int[]postorder) {
		HashMap<Integer,Integer>map=new HashMap<>();
		for(int i=0;i<inorder.length;i++) {
			map.put(inorder[i],i);
		}
		return builderTreeHelper(inorder,0,inorder.length,postorder,0,postorder.length,map);
	}

	private static TreeNode builderTreeHelper(int[] inorder, int i_start, int i_end, int[] postorder, int p_start, int p_end,HashMap<Integer,Integer>map) {
		
		if(p_start==p_end) return null;
		int root_val=postorder[p_end-1];
		TreeNode root=new TreeNode(root_val);
		int i_root_index=map.get(root_val);
		int leftNum=i_root_index-i_start;
		root.left = builderTreeHelper(inorder, i_start, i_root_index, postorder, p_start, p_start + leftNum, map);
	    root.right = builderTreeHelper(inorder, i_root_index + 1, i_end, postorder, p_start + leftNum, p_end - 1,map);
		return root;
	}
	public static void main(String args[]) {
		int[] preorder= {9,3,15,20,7};
		int[] inorder= {9,15,7,20,3};
		
		TreeNode ans=buildTree(preorder,inorder);
		System.out.println(ans.val);
	}
}

106.Construct Binary Tree from Inorder and Postorder Traversal

参考文献

1.https://zhuanlan.zhihu.com/p/74277078

相关标签: LeetCode