LeetCode114 二叉树展开为链表 ---二叉树题 三种解法 (递归) (迭代) (前驱节点)

转载 作者：知者 更新时间：2024-03-13 04:37:40 26 4

class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        preorderTraversal(root, list);
        for (int i = 0; i < list.size() - 1; i++) {
            list.get(i).left = null;
            list.get(i).right = list.get(i+1);
        }
    }
    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
        if (root == null) return;
        list.add(root);
        preorderTraversal(root.left, list);
        preorderTraversal(root.right, list);
    }
}

class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return;
        Stack<TreeNode> stack = new Stack<>();
        List<TreeNode> list = new ArrayList<>();
        TreeNode cur = root;
        //cur 不为空 或 栈 不为空 进入循环
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);//cur不为空就入栈
                list.add(cur);//入栈的同时插入到list中
                cur = cur.left;//根->左的顺序
            }
            TreeNode top = stack.pop();
            cur = top.right;//根->左 结束之后 就开始 右
        }
        //遍历list
        for (int i = 0; i < list.size() - 1; i++) {
            list.get(i).left = null;
            list.get(i).right = list.get(i+1);
        }
    }
}

class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return;
        TreeNode cur = root;
        TreeNode curNext = null;
        while (cur != null){
            if(cur.left != null){
                curNext = cur.left;
            	TreeNode pre = curNext;
            	//让pre指向左子树的最右节点
           		while (pre.right != null){
                	pre = pre.right;
            	}
            	//让左子树最右节点和右子树链接
	           	pre.right = cur.right;
            	//让根节点的左边断开
            	cur.left = null;
            	//让根节点的右子树连接左子树
            	cur.right = curNext;
            }
            cur = cur.right;
        }
    }

}

26 4 0

• Leetcode: Binary Tree Paths(LeetCode：二叉树路径)

  我正在解决以下leetcode问题：。。递归解是平凡的，所以我试着想出迭代解。下面是我的解决方案：。问题是：代码相对冗长，难以阅读。我的想法是跟踪从顶部到当前节点的整个路径。但这与标准DFS不同，因为

• Leetcode: Binary Tree Paths(LeetCode：二叉树路径)

  我正在解决以下leetcode问题：。。递归的解决方案是微不足道的，所以我试图拿出迭代的解决方案。下面是我的解决方案：。问题是：代码相对冗长，难以阅读。我的想法是跟踪从顶部到当前节点的整个路径。但这与

• javascript - Javascript 中的两个 Sum Leetcode - 代码看起来正确，但 Leetcode 说它是错误的

  我正在处理 'Two Sum' problem in Leetcode . 我确信这段代码是正确的，我已经在 Repl 中对其进行了测试，它看起来是正确的，但 Leetcode 给了我一个错误。 这是

• python - LeetCode 762 为什么单独的代码在 Jupyter Notebook 中有效，而在 Leetcode 中无效

  我正在研究 leetcode“762. 二进制表示中设置位的质数”，并且我测试了我的代码在 Jupiter Notebook 上运行良好，当我迁移到 leetcode 时，它​​显示 null 作为最

• LeetCode：搜索二维矩阵题解

  题干 请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征： 每一行的数字都从左到右排序 每一行的第一个数字都比上一行最后一个数字大 用例 例如对于下面矩阵： [ [1,

• LeetCode 单调栈内容小结

  LeetCode Monotone Stack Summary 单调栈小结 所谓的单调栈 Monotone Stack，就是栈内元素都是单调递增或者单调递减的，有时候需要严格的单调递增或递减，根据

• LeetCode 二叉树相关Easy题 --- 二叉树

  第一题: 合并二叉树 LeetCode 617 : 合并二叉树 描述: 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。 你需要将他们合并为一个新的二叉树。合并的

• 和为k的子数组 LeetCode 560

  和为k的子数组 LeetCode 560 和为k的不重复子数组个数(包含不连续)： 和为k的子数组 LeetCode 560 Example 1: Input:nums=[1,1,1],k=2  Ou

• [Leetcode]13. 罗马数字转整数

  1.题目描述： 难度：简单 描述： 罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。 字符 数值 I 1 V 5 X

• [Leetcode]9. 回文数

  1.题目描述： 难度：简单 描述： 给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 例如，1

• [Leetcode]26. 删除有序数组中的重复项

  一、题目描述 难道：简单 描述： 给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。 由于在

• [Leetcode]14. 最长公共前缀

  一、题目描述 难度：简单 描述： 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀，返回空字符串 “”。 示例 1： 输入：strs = ["flower","flow","flig

• [Leetcode]21. 合并两个有序链表

  一、题目描述 难度：简单 描述： 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1： 输入：l1 = [1,2,4], l2 = [1,3,4

• 【LeetCode】 - 20.有效的括号

  @TOC 题目描述 给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序

• javascript - 合并两个列表 LeetCode

  我已经在 Repl.it 网站上解决了这个问题，但是当我在 LeetCode 上提交代码时，它给出了一个 typeError，我将把它粘贴在这里: Line 29 in solution.js

• javascript - leetcode 合并排序数组

  var merge = function(nums1, m, nums2, n) { //contcating two array let array = nums2.concat(

• javascript - leetcode 两数相加算法

  我正在做以下leetCode问题:https://leetcode.com/problems/add-two-numbers/ 我不确定为什么我的一个测试用例失败了 所以问题是 You are giv

• python - Leetcode 在无可争议的正确答案时声称错误答案

  我正在尝试完成 Leetcode 上的 189. 旋转数组问题。这是我写的代码: class Solution(object): def rotate(self, nums, k):

• java - LeetCode 中的递归和回溯是如何工作的？

  该函数将反向打印链表的节点: void recur(ListNode head) { if(head == null) return; recur(head.next); tm

• python - Leetcode 在无可争议的正确答案时声称错误答案

  我正在尝试完成 Leetcode 上的 189. 旋转数组问题。这是我写的代码: class Solution(object): def rotate(self, nums, k):