Leetcode 从中序与后序遍历序列构造二叉树

java 递归实现

1. class Solution {
2.     private HashMap<Integer, Integer> inorderIndexMap;
3.     private int postorderIndex;
5.     public TreeNode buildTree(int[] inorder, int[] postorder) {
6.         inorderIndexMap = new HashMap<>();
7.         postorderIndex = postorder.length - 1;
9.         for(int i = 0; i < inorder.length; i++) {
10.             inorderIndexMap.put(inorder[i], i);
11.         }
13.         return Helper(postorder, 0, inorder.length - 1);
14.     }
16.     private TreeNode Helper(int[] postorder, int inorderStart, int inorderEnd) {
17.         if(inorderStart > inorderEnd) return null;
18.         //首先确定根节点的值
19.         int rootValue = postorder[postorderIndex--];
20.         TreeNode root = new TreeNode(rootValue);
22.         //获取根节点在中序遍历中的索引，用于后面划分左右子树
23.         int inorderIndex = inorderIndexMap.get(rootValue);
25.         // 递归构建右子树和左子树
26.         // 注意：需要先构建右子树，因为后序遍历的顺序是左右根
27.         root.right = Helper(postorder, inorderIndex + 1, inorderEnd);
28.         root.left = Helper(postorder, inorderStart, inorderIndex - 1);
30.         return root;
31.     }
32. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。