题解 | #牛群的树形结构展开II#

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
     List<TreeNode> vt; 
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return TreeNode类
     */
    public TreeNode flattenII (TreeNode root) {
        // write code here
        if (root == null) return null;

        vt = new ArrayList<>();
        dfs(root);
        int n = vt.size();
        for (int i = 1; i < n; i++) {
            vt.get(i - 1).right = vt.get(i);
            vt.get(i - 1).left = null;
        }
        vt.get(n - 1).left = vt.get(n - 1).right = null;

        return vt.get(0);
    }

    private void dfs(TreeNode root) {
        if (root == null) return;

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

知识点：

1. 二叉树的结构定义：定义了一个 TreeNode 结构体，包含一个整数值 val，以及左右子节点指针 left 和 right。
2. 二叉树的展开：将二叉树展开为一个只有右子节点的链表形式。
3. 深度优先搜索（DFS）：使用递归的方式遍历二叉树。
4. 链表操作：将二叉树的节点连接成链表形式。

解题思路：

1. 定义了一个 TreeNode 结构体，包含一个整数值 val，以及左右子节点指针 left 和 right。
2. 创建了一个 Solution 类，包含了展开二叉树的方法 flattenII。
3. flattenII 方法接收一个根节点 root，并返回展开后的新树的根节点。如果根节点为空，直接返回空。使用一个列表 vt 来辅助链表操作。使用深度优先搜索（DFS）遍历二叉树，将节点按照遍历顺序添加到列表 vt 中。遍历列表 vt，将每个节点的左子节点置为空，并将节点的右子节点指向下一个节点。将最后一个节点的左子节点和右子节点都置为空。返回展开后的树的根节点。