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

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

        List<TreeNode> list = new ArrayList<>();
        dfs(root, list);

        int n = list.size();
        for (int i = 1; i < n; i++) {
            list.get(i - 1).right = list.get(i);
            list.get(i - 1).left = null;
        }

        list.get(n - 1).left = list.get(n - 1).right = null;
        return list.get(0);
    }

    private void dfs(TreeNode root, List<TreeNode> list) {
        if (root == null) return;

        dfs(root.left, list);
        list.add(root);
        dfs(root.right, list);
    }
}

Java代码

该题目使用深度优先搜索（DFS）实现了二叉树的展开操作。给定一个二叉树，需要将其展开为链表，其中右子树要跟在左子树的后面，而原先的左子树变为新的右子树。

在代码中，flattenII 方法接收一个 TreeNode 类型的参数 root，表示二叉树的根节点，返回展开后的二叉树的根节点。

代码中使用了递归的方式进行先序遍历。具体步骤如下：

1. 如果 root 为空，直接返回 null。
2. 创建一个 List<TreeNode> 类型的变量 list，用于存储遍历过程中的节点。
3. 调用递归函数 dfs 实现先序遍历，传入 root 和 list 作为参数。
4. 遍历结束后，获取 list 的大小，记为 n。
5. 对 list 中的节点进行处理：将第 i-1 个节点的右子节点指向第 i 个节点。将第 i-1 个节点的左子节点设为 null。
6. 将最后一个节点的左子节点和右子节点设为 null。
7. 返回 list 的第一个节点作为展开后的二叉树的根节点。

题目考察了对二叉树的遍历、递归算法和指针操作的理解和应用。通过先序遍历获取节点顺序，并修改节点的指针，将二叉树展开成链表结构。