题目如下:
Given preorder and inorder traversal of a tree, construct the binary tree. eg: preorder = [3,9,20,15,7] inorder = [9,3,15,20,7] return: 3 / \ 9 20 / \ 15 7
已知二叉树的前序遍历序列和中序遍历序列,让我们写出二叉树的结构。
如所给例子所示,首先取前序遍历序列preorder中的第一个元素3,则在中序遍历序列中[9]是3的左子树,[15,20,7]是3的右子树。再看preorder,20是[20,15,7]的根,再看inorder,15是20的左子树,7是20的右子树。
代码实现如下:
/** * Definition for a binary tree node. * public class TreeNode { * int val * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { return buildTree(0, 0, preorder.length - 1, preorder, inorder); } public TreeNode buildTree(int preStart, int inStart, int inEnd, int[] preorder, int[] inorder) { if (preStart >= preorder.length || inStart > inEnd) { return null; } TreeNode root = new TreeNode(preorder[preStart]); int rootIndex = inStart; for (int i = inStart; i <= inEnd; i++) { if (inorder[i] != preorder[preStart]) { continue; } rootIndex = i; break; } TreeNode left = buildTree(preStart + 1, inStart, rootIndex - 1, preorder, inorder); TreeNode right = buildTree(preStart + (rootIndex - inStart) + 1, rootIndex + 1, inEnd, preorder, inorder); root.left = left; root.right = right; return root; } }
- 本文固定链接: https://weiguangli.com/archives/400
- 转载请注明: lwg0452 于 Weiguang的博客 发表
捐 赠如果您觉得这篇文章有用处,请支持作者!鼓励作者写出更好更多的文章!