题目一:
105. 从前序与中序遍历序列构造二叉树https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
思路:依据前序遍历的根左右和中序遍历的左根右, 且根左长度=左根
代码:文章来源地址https://www.toymoban.com/news/detail-684536.html
class Solution {
HashMap<Integer, Integer> map ;
public TreeNode buildTree(int[] preorder, int[] inorder) {
map = new HashMap<>();
int n = preorder.length;
for (int i = 0; i < n; i++)
map.put(inorder[i], i);
return mybuildTree(preorder, 0, n - 1, inorder, 0, n - 1);
}
private TreeNode mybuildTree(int[] preorder, int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
if (preBegin > preEnd || inBegin > inEnd) return null;
// 前序遍历的头结点一定是根结点 比如pre_rootIndex = 0
int pre_rootIndex = preBegin;
// 根据根结点值获取到它在中序遍历的索引值 preorder[pre_rootIndex就是当前根节点值
int inorder_rootIndex = map.get(preorder[pre_rootIndex]);
// 构建根结点
TreeNode root = new TreeNode(preorder[pre_rootIndex]);
// 截取长度 得到左子树的元素个数
int len = inorder_rootIndex - inBegin;
// 注意起始, 前序遍历左子树的开始节点是根节点的下一个,结束节点是加上左子树长度, 中序遍历的好理解
root.left = mybuildTree(preorder, preBegin + 1, preBegin + len, inorder, inBegin, inorder_rootIndex - 1);
// 前序遍历右子树就是(根+左子树)的长度即原先起始+1+len
root.right = mybuildTree(preorder, preBegin + 1 + len, preEnd, inorder, inorder_rootIndex + 1, inEnd);
return root;
}
}
题目二:
14. 二叉树展开为链表https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/
思路:前序遍历文章来源:https://www.toymoban.com/news/detail-684536.html
代码:
class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<>();
preorder(root, list);
int size = list.size();
for (int i = 1 ; i < size; i++) {
TreeNode pre = list.get(i - 1), cur = list.get(i);
// 保证父节点的左子树为null 右子树为下一个索引为i的值
pre.left = null;
pre.right = cur;
}
}
// 前序遍历
private void preorder(TreeNode root, List<TreeNode> list){
if (root == null) return;
list.add(root);
preorder(root.left, list);
preorder(root.right, list);
}
}
到了这里,关于LeetCode 热题 100(七):105. 从前序与中序遍历序列构造二叉树、14. 二叉树展开为链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!