关于leetcode:leetcode-114-Flatten-Binary-Tree-to-Linked-List-二叉树展开为链表简单

2次阅读

共计 1105 个字符，预计需要花费 3 分钟才能阅读完成。

给你二叉树的根结点 root，请你将它开展为一个单链表：

开展后的单链表应该同样应用 TreeNode，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null。
开展后的单链表应该与二叉树先序遍历程序雷同。

示例 1：

输出：root = [1,2,5,3,4,null,6]
输入：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输出：root = []
输入：[]

示例 3：

输出：root = [0]
输入：[0]

提醒：

树中结点数在范畴 [0, 2000] 内
-100 <= Node.val <= 100

进阶：你能够应用原地算法（O(1) 额定空间）开展这棵树吗？

起源：力扣（LeetCode）
链接：https://leetcode.cn/problems/…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

思路：非迭代版实现，从根节点开始登程，先检测其左子节点是否存在，如存在则将根节点和其右节点断开，将左子节点及其前面所有构造一起连贯到右子节点的地位，把原右子节点连到原左子节点为最初面的右子节点之后。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) {this.val = val;}
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {public void flatten(TreeNode root) {
        // 上面再来看非迭代版本的实现，这个办法是从根节点开始登程，先检测其左子结点是否存在，如存在则将根节点和其右子节点断开，// 将左子结点及其前面所有构造一起连到原右子节点的地位，把原右子节点连到元左子结点最初面的右子节点之后。代码如下：TreeNode cur = root;
        while (cur != null) {if (cur.left != null) {
                TreeNode p = cur.left;
                while (p.right != null) {p = p.right;}
                p.right = cur.right;
                cur.right = cur.left;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
}