leetcode 从前序与中序遍历序列构造二叉树

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

1. 题目：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

2. 思路：
   二叉树前序遍历的顺序为：

   先遍历根节点；随后递归地遍历左子树；最后递归地遍历右子树。
   

   二叉树中序遍历的顺序为：

   先递归地遍历左子树；随后遍历根节点；最后递归地遍历右子树。
   

   因此，只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

3. 代码

   class Solution {int[] preorder;Map<Integer,Integer> map = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {this.preorder = preorder;for(int i = 0;i < inorder.length;i++){map.put(inorder[i],i);}return cur(0,0,inorder.length-1);}public TreeNode cur(int root, int left, int right){if(left > right) return null;//建立根节点TreeNode node = new TreeNode(preorder[root]);int i = map.get(node.val);// 递归建立左子树node.left = cur(root + 1,left,i-1);// 递归建立右子树node.right = cur(root + i - left + 1,i + 1,right);return node;}
   }
   

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！