LeetCode 热题 100（七）：105. 从前序与中序遍历序列构造二叉树、14. 二叉树展开为链表

题目一：

105. 从前序与中序遍历序列构造二叉树https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

思路：依据前序遍历的根左右和中序遍历的左根右， 且根左长度＝左根

代码：

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 = 0int 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/

思路：前序遍历

代码：

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);} 
}