How to Construct Binary Search Tree from Preorder Traversal? (C+
- 时间:2020-10-11 16:01:36
- 分类:网络文摘
- 阅读:90 次
Return the root node of a binary search tree that matches the given preorder traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val. Also recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)
Input: [8,5,1,7,10,12]
Binary Search Tree
Output: [8,5,10,1,7,null,12]Note:
1 <= preorder.length <= 100
The values of preorder are distinct.
Construct Binary Search Tree Algorithm from Preorder
The first element in the preorder traversal is the root node, and its left elements are always smaller than its value and the right elements are larger.
Therefore, we can find the index where the value is bigger than the root, thus separating the left and right nodes.
Recursively, we can construct the binary search tree by finding the pivot index.
The following C++ implementation uses a helper function which adds two parameter i.e. left and right index forming current sub-tree.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* bstFromPreorder(vector<int>& preorder) { return helper(preorder, 0, preorder.size() - 1); } TreeNode* helper(vector<int>& preorder, int left, int right) { if (left > right) return NULL; int root = preorder[left]; int r = right + 1; for (int i = left + 1; i <= right; ++ i) { if (preorder[i] >= root) { // find the first of right node r = i; break; } } TreeNode* rootNode = new TreeNode(root); rootNode->left = helper(preorder, left + 1, r - 1); rootNode->right = helper(preorder, r, right); return rootNode; } }; |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* bstFromPreorder(vector<int>& preorder) { return helper(preorder, 0, preorder.size() - 1); } TreeNode* helper(vector<int>& preorder, int left, int right) { if (left > right) return NULL; int root = preorder[left]; int r = right + 1; for (int i = left + 1; i <= right; ++ i) { if (preorder[i] >= root) { // find the first of right node r = i; break; } } TreeNode* rootNode = new TreeNode(root); rootNode->left = helper(preorder, left + 1, r - 1); rootNode->right = helper(preorder, r, right); return rootNode; } };
The time complexity is O(N) where all nodes need to be visited exactly once and the space complexity is also O(N) where the binary search tree may be degraded into a singly-linked list.
Converting to Java, the following is the Java implementation to construct a binary search tree from a preorder traversal.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode bstFromPreorder(int[] preorder) { return helper(preorder, 0, preorder.length - 1); } private TreeNode helper(int[] preorder, int left, int right) { if (left > right) return null; int root = preorder[left]; int r = right + 1; for (int i = left + 1; i <= right; ++ i) { if (preorder[i] >= root) { r = i; break; } } TreeNode rootNode = new TreeNode(root); rootNode.left = helper(preorder, left + 1, r - 1); rootNode.right = helper(preorder, r, right); return rootNode; } } |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode bstFromPreorder(int[] preorder) { return helper(preorder, 0, preorder.length - 1); } private TreeNode helper(int[] preorder, int left, int right) { if (left > right) return null; int root = preorder[left]; int r = right + 1; for (int i = left + 1; i <= right; ++ i) { if (preorder[i] >= root) { r = i; break; } } TreeNode rootNode = new TreeNode(root); rootNode.left = helper(preorder, left + 1, r - 1); rootNode.right = helper(preorder, r, right); return rootNode; } }
We can use Arrays.copyOfRange(oldArray, fromIndex, toIndex) to return a partial copy of the array, thus we don’t need to have the helper function, instead, we can just recursively call the existing method with copies (portion) of the preorder traversal – e.g. of the sub trees.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode bstFromPreorder(int[] preorder) { if (preorder == null || preorder.length == 0) return null; int root = preorder[0]; int r = preorder.length; for (int i = 1; i < preorder.length; ++ i) { if (preorder[i] >= root) { r = i; break; } } TreeNode rootNode = new TreeNode(root); int[] leftTree = null; if (r >= 1) { leftTree = Arrays.copyOfRange(preorder, 1, r); } int[] rightTree = Arrays.copyOfRange(preorder, r, preorder.length); rootNode.left = bstFromPreorder(leftTree); rootNode.right = bstFromPreorder(rightTree); return rootNode; } } |
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public TreeNode bstFromPreorder(int[] preorder) { if (preorder == null || preorder.length == 0) return null; int root = preorder[0]; int r = preorder.length; for (int i = 1; i < preorder.length; ++ i) { if (preorder[i] >= root) { r = i; break; } } TreeNode rootNode = new TreeNode(root); int[] leftTree = null; if (r >= 1) { leftTree = Arrays.copyOfRange(preorder, 1, r); } int[] rightTree = Arrays.copyOfRange(preorder, r, preorder.length); rootNode.left = bstFromPreorder(leftTree); rootNode.right = bstFromPreorder(rightTree); return rootNode; } }
The Python’s implementation can be found here (using the list comprehension): How to Construct Binary Search Tree from Preorder Traversal in Python?
Related Binary Tree Construction Algorithms
You may also like the following posts on the similar tree problems.
- Recursive Algorithm to Construct Binary Tree from Preorder and Postorder Traversal
- How to Construct Binary Search Tree from Preorder Traversal in Python?
- Algorithm to Construct Binary Tree from Preorder and Inorder Traversal
- How to Construct Binary Search Tree from Preorder Traversal? (C++ and Java)
- How to Construct String from Binary Tree?
- How to Balance a Binary Search Tree using Recursive Inorder Traversal Algorithm?
- How to Construct the Maximum Binary Tree using Divide-and-Conquer Recursion Algorithm?
- How to Construct Binary Tree from Inorder and Postorder Traversal using Depth First Search Algorithm (Recursion)?
- How to Construct Binary Tree from String (Binary Tree Deserialization Algorithm)
–EOF (The Ultimate Computing & Technology Blog) —
推荐阅读:数学题:用一条56米长的栅栏围一个花园 数学题:小李是卖鞋店老板 数学题:学校把两捆树苗分给三个年级种植 数学题:如果x分之1加y分之1等于12分之5 数学题:一枚2分的硬币重1克 数学题:水果店买来两筐苹果 数学题:一个长方形铁皮,长为32厘米 数学题:小明家住7楼 数学题:有软、硬两种糖果放成一堆 创新自信与成功
- 评论列表
-
- 添加评论