【LeetCode-中等题】114. 二叉树展开为链表

这篇具有很好参考价值的文章主要介绍了【LeetCode-中等题】114. 二叉树展开为链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

题目

【LeetCode-中等题】114. 二叉树展开为链表,力扣,# 中等题,leetcode,算法,链表

方法一:前序遍历(构造集合) + 集合(构造新树)

 List<TreeNode> res = new ArrayList<>();
    public void flatten(TreeNode root) {
        dfs(root);
        for(int i  = 0 ; i <res.size() ; i++){
            if(i == res.size()-1){//处理最后一个节点
                res.get(i).left = null;
                res.get(i).right = null;
                break;
            }
            res.get(i).left = null;
            res.get(i).right = res.get(i+1);
        }
    }
        //前序遍历
    public void dfs(TreeNode root) {
        if(root == null ) return ;

        res.add(root);
        dfs(root.left);
        dfs(root.right);
    }

方法二:原地构建

  1. 将左子树插入到右子树的地方
  2. 将原来的右子树接到左子树的最右边节点
  3. 考虑新的右子树的根节点,一直重复上边的过程,直到新的右子树为 null
public void flatten(TreeNode root) {
        while(root !=null){
         //左子树为 null,直接考虑下一个节点
        if (root.left == null) {
            root = root.right;
        } else {
             // 找左子树最右边的节点
             TreeNode  pre = root.left;
             while(pre.right !=null){
                 pre =pre.right;
             }
             //将原来的右子树接到左子树的最右边节点
              pre.right = root.right;
             // 将左子树插入到右子树的地方
              root.right = root.left;
              root.left = null;
            // 考虑下一个节点
              root = root.right;
        }
    }
  }

【LeetCode-中等题】114. 二叉树展开为链表,力扣,# 中等题,leetcode,算法,链表文章来源地址https://www.toymoban.com/news/detail-683976.html

方法三:前序遍历–迭代(构造集合) + 集合(构造新树)

 public void flatten(TreeNode root) {
        List<TreeNode> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        while(!stack.isEmpty() || root != null){
            while(root != null) {
                res.add(root);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }
        for(int i  = 0 ; i <res.size() ; i++){
            if(i == res.size()-1){//处理最后一个节点
                res.get(i).left = null;
                res.get(i).right = null;
                break;
            }
            res.get(i).left = null;
            res.get(i).right = res.get(i+1);
        }
    }

到了这里,关于【LeetCode-中等题】114. 二叉树展开为链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • LeetCode_二叉树_DFS_中等_129.求根节点到叶节点数字之和

    给你一个二叉树的根节点 root ,树中每个节点都存放有一个 0 到 9 之间的数字。 每条从根节点到叶节点的路径都代表一个数字:例如,从根节点到叶节点的路径 1 - 2 - 3 表示数字 123。 计算从根节点到叶节点生成的所有数字之和 。 叶节点是指没有子节点的节点。 示例 1: 输

    2024年02月08日
    浏览(41)
  • 每天一道leetcode:剑指 Offer 34. 二叉树中和为某一值的路径(中等&图论&深度优先遍历&递归)

    给你二叉树的根节点 root 和一个整数目标和 targetSum ,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。 叶子节点 是指没有子节点的节点。 树中节点总数在范围 [0, 5000] 内 -1000 = Node.val = 1000 -1000 = targetSum = 1000 使用递归深度优先遍历,使用前序遍历,在遍历途

    2024年02月12日
    浏览(49)
  • LeetCode(力扣)236. 二叉树的最近公共祖先Python

    https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/

    2024年02月10日
    浏览(38)
  • 【LeetCode】(力扣) c/c++刷题-145. 二叉树的后序遍历

    来源:力扣(LeetCode) 链接: 力扣  

    2024年02月01日
    浏览(65)
  • 【LeetCode力扣】297. 二叉树的序列化与反序列化

      目录 1、题目介绍 2、解题思路  2.1、详细过程图解 2.2、代码描述   2.3、完整代码   原题链接:297. 二叉树的序列化与反序列化 - 力扣(LeetCode)   示例 1: 输入: root = [1,2,3,null,null,4,5] 输出: [1,2,3,null,null,4,5] 示例 2: 输入: root = [ ] 输出: [ ] 示例 3: 输入: root = [1

    2024年02月08日
    浏览(65)
  • 【Leetcode】二叉树的最近公共祖先,二叉搜索树转换成排好序的双向链表,前序遍历与中序遍历构造二叉树

    二叉树的最近公共祖先  观察上图,节点1和节点4的最近公共祖先是3,这是不是很像相交链表的问题,关于相交链表,曾经我在另一篇文章里写到过,读者可以参考:反转链表 合并链表 相交链表 但是要转换成相交链表,就要从后向前遍历,如果节点中还存在一个指针,指向

    2024年02月14日
    浏览(36)
  • 趣说数据结构(练习2) —— 顺序表/链表力扣刷题(中等难度)

    力扣原题:https://leetcode.cn/problems/reverse-linked-list-ii/ 题目描述 给你单链表的头指针 head 和两个整数 left 和 right ,其中 left = right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。 示例 1 输入:head = [1,2,3,4,5], left = 2, right = 4 输出:[1,4,3,2,5] 示例 2 输入:h

    2024年02月01日
    浏览(56)
  • 【LeetCode力扣】11. 盛最多水的容器 (中等)

      目录 1、题目介绍 2、解题 2.1、解题思路  2.2、图解说明  2.3、解题代码 原题链接: 11. 盛最多水的容器 - 力扣(LeetCode) 示例 2: 提示: n == height.length 2 = n = 105 0 = height[i] = 104 这道题最优的方法就是用双指针,我们可以用指针 left 和指针 right 分别指向数组 height[ ] 的第一

    2024年02月06日
    浏览(47)
  • 【LeetCode-中等题】148. 排序链表

    把链表放到List集合,排好序,再依据List集合创建一个新有序链表返回就行了 优先队列 往这个优先队列中插入元素时,会按照节点 val 属性的大小顺序进行排序,即小的节点排在前面,大的节点排在后面。依次谈栈再创建新链表 优先队列声明 先找到中间点 按中间点切割链表

    2024年02月11日
    浏览(42)
  • 力扣刷题-二叉树-合并二叉树

    合并二叉树是操作两棵树的题目里面很经典的,如何对两棵树遍历以及处理? 给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为

    2024年01月17日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包