Leetcode 之Construct Binary Tree(52)
LeetCode Tree Binary 52 Construct
2023-09-14 08:57:33 时间
根据先序和中序构造二叉树、根据中序和后序构造二叉树,基础题,采用递归的方式解决,两题的方法类似。需要注意的是迭代器的用法。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
//先序和中序 TreeNode *buildTree(vector<int>& preorder, vector<int>& inorder) { return buildTree(begin(preorder), end(preorder), begin(inorder), begin(inorder)); } template<typename InputIterator> TreeNode *buildTree(InputIterator pre_first, InputIterator pre_last, InputIterator in_first, InputIterator in_last) { if (pre_first == pre_last)return nullptr; if (in_first == in_last)return nullptr; //先序第一个为根结点 auto root = new TreeNode(*pre_first); //查找根结点在中序的位置,返回的是迭代器 auto intRootPos = find(in_first, in_last, *pre_first); //得到根结点的左半部分 auto leftSize = distance(in_first, intRootPos); //递归构造,注意去掉根结点 root->left = buildTree(next(pre_first), next(pre_first, leftSize), in_first, next(in_first, leftSize)); root->right = buildTree(next(pre_first, leftSize), pre_last, next(intRootPos), in_last); return root; }
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
//中序和后序 TreeNode *buildTree1(vector<int>& inorder, vector<int>& postorder) { return buildTree1(begin(inorder), end(inorder), begin(postorder), begin(postorder)); } template<typename InputIterator> TreeNode *buildTree1(InputIterator in_first, InputIterator in_last, InputIterator post_first, InputIterator post_last) { if (in_first == in_last)return nullptr; if (post_first == post_last)return nullptr; //后序最后一个为根结点 const auto val = *prev(post_last) auto root = new TreeNode(val); //查找根结点在中序的位置,返回的是迭代器 auto intRootPos = find(in_first, in_last, val); //得到根结点的左半部分 auto leftSize = distance(in_first, intRootPos); //递归构造,注意去掉根结点 root->left = buildTree(in_first, intRootPos, post_first, next(post_first, leftSize)); root->right = buildTree(next(intRootPos), in_last, next(post_first,leftSize), prev(post_last)); return root; }
相关文章
- Java实现 LeetCode 96 不同的二叉搜索树
- Java实现LeetCode 111. Minimum Depth of Binary Tree
- LeetCode:145_Binary Tree Postorder Traversal | 二叉树后序遍历 | Hard
- [LeetCode] Binary Tree Right Side View
- leetcode - Construct Binary Tree from Inorder and Postorder Traversal
- [LeetCode] 104. Maximum Depth of Binary Tree ☆(二叉树的最大深度)
- [LeetCode] 99. Recover Binary Search Tree(复原BST) ☆☆☆☆☆
- [LeetCode]*124.Binary Tree Maximum Path Sum
- LeetCode——Binary Tree Level Order Traversal II
- [LeetCode] Count Complete Tree Nodes
- LeetCode——Symmetric Tree
- LeetCode之Binary Tree Level Order Traversal 层序遍历二叉树
- leetcode dfs Flatten Binary Tree to Linked List
- [LeetCode] Flatten Binary Tree to Linked List
- LeetCode 235: Lowest Common Ancestor of a Binary Search Tree
- leetcode 107. Binary Tree Level Order Traversal II
- leetcode 257. Binary Tree Paths
- leetcode 108. Convert Sorted Array to Binary Search Tree
- leetcode 543. Diameter of Binary Tree
- leetcode 690. Employee Importance——本质上就是tree的DFS和BFS
- leetcode 104. Maximum Depth of Binary Tree
- leetcode 669. Trim a Binary Search Tree