如何做网站静态页面,中国机械加工网站,企业邮箱怎么注册?,钢丝网片题目一#xff1a; 105. 从前序与中序遍历序列构造二叉树https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
思路#xff1a;依据前序遍历的根左右和中序遍历的左根右#xff0c; 且根左长度#xff1d;左根
代码#xff1a;
…题目一 105. 从前序与中序遍历序列构造二叉树https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
思路依据前序遍历的根左右和中序遍历的左根右 且根左长度左根
代码
class Solution {HashMapInteger, 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);// 前序遍历右子树就是(根左子树)的长度即原先起始1len 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) {ListTreeNode 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, ListTreeNode list){if (root null) return;list.add(root);preorder(root.left, list);preorder(root.right, list);}
}
