题解 | #牛群的树形结构展开II# java
牛群的树形结构展开II
https://www.nowcoder.com/practice/3e89ca58f76d4e6aa44cf29569017410
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
,表示二叉树的根节点,返回展开后的二叉树的根节点。
代码中使用了递归的方式进行先序遍历。具体步骤如下:
- 如果
root
为空,直接返回null
。 - 创建一个
List<TreeNode>
类型的变量list
,用于存储遍历过程中的节点。 - 调用递归函数
dfs
实现先序遍历,传入root
和list
作为参数。 - 遍历结束后,获取
list
的大小,记为n
。 - 对
list
中的节点进行处理:将第 i-1 个节点的右子节点指向第 i 个节点。将第 i-1 个节点的左子节点设为 null。 - 将最后一个节点的左子节点和右子节点设为
null
。 - 返回
list
的第一个节点作为展开后的二叉树的根节点。
题目考察了对二叉树的遍历、递归算法和指针操作的理解和应用。通过先序遍历获取节点顺序,并修改节点的指针,将二叉树展开成链表结构。