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

这篇具有很好参考价值的文章主要介绍了LeetCode 热题 100(七):105. 从前序与中序遍历序列构造二叉树、14. 二叉树展开为链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目一:

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/

思路:前序遍历

代码:

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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包