关于java:LeetCode114二叉树展开为链表

38次阅读

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

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

开展后的单链表应该同样应用 TreeNode，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null。

开展后的单链表应该与二叉树先序遍历程序雷同。

示例阐明请见 LeetCode 官网。

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

解法一：递归

应用递归的形式求解，递归过程如下：

如果以后根节点为 null 时，间接返回；

如果以后根节点的左右子节点都为空时，不须要调整，间接返回；

如果以后根节点的左子树为空，则只须要递归解决以后根节点的右子树；

如果以后根节点的右子树为空时，则须要递归解决以后根节点的左子树，而后将以后根节点的左子节点指向 null，右子节点指向解决后的左子树；

如果以后根节点的左右子树都不为空，则别离递归解决以后根节点的左右子树，而后将根节点的左子节点指向 null，右子节点指向解决后的左子树，而后将左子树的最初一个节点指向解决后的右子树。

import com.kaesar.leetcode.TreeNode;

public class LeetCode_114 {
    /**
     * 递归
     *
     * @param root
     */
    public static void flatten(TreeNode root) {
        // 以后根节点为 null 时，间接返回
        if (root == null) {return;}
        // 以后根节点的左右子节点都为空时，不须要调整，间接返回
        if (root.left == null && root.right == null) {return;}
        if (root.left == null) {
            // 以后根节点的左子树为空，则只须要递归解决以后根节点的右子树
            flatten(root.right);
            return;
        }
        if (root.right == null) {
            // 以后根节点的右子树为空时，则须要递归解决以后根节点的左子树，而后将以后根节点的左子节点指向 null，右子节点指向解决后的左子树
            TreeNode left = root.left;
            flatten(left);
            root.right = left;
            root.left = null;
            return;
        }
        // 如果以后根节点的左右子树都不为空
        TreeNode left = root.left;
        // 递归解决左子树，并找到解决后的最初一个节点
        flatten(left);
        TreeNode leftLast = left;
        while (leftLast.right != null) {leftLast = leftLast.right;}
        TreeNode right = root.right;
        // 递归解决右子树
        flatten(right);
        // 最初将根节点的左子节点指向 null，右子节点指向解决后的左子树，而后将左子树的最初一个节点指向解决后的右子树
        root.right = left;
        leftLast.right = right;
        root.left = null;
    }

    public static void main(String[] args) {TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(6);

        System.out.println("开展为链表之前");
        root.print();
        System.out.println("开展为链表之后");
        flatten(root);
        root.print();}
}