题解 | #牛群的树形结构展开# java
牛群的树形结构展开
https://www.nowcoder.com/practice/07caea5438394f58afbe72cbe2eb2189
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 flattenTree (TreeNode root) { // write code here if (root == null) { return null; } TreeNode p = root; Stack<TreeNode> stack = new Stack<>(); while (p != null) { if (p.right != null) { stack.push(p.right); } TreeNode pl = p.left; p.left = null; if (pl == null) { if (stack.isEmpty()) { break; } pl = stack.pop(); } p.right = pl; p = pl; } return root; } }
Java编程语言。
这个题目考察的知识点是二叉树的遍历以及使用栈进行迭代遍历。具体来说,该代码实现了将二叉树展开为链表的功能。在展开后的链表中,右子树将会跟在左子树的后面,而原先的左子树会变为新的右子树。
对于给定的二叉树,该代码使用迭代的方式进行先序遍历,并且在遍历的过程中完成链表的展开。具体步骤如下:
- 对于当前节点p,如果p的右子节点不为空,则将其入栈,以便在之后处理。
- 将p的左子节点设为null,并将p的右子节点设置为p的原左子节点。
- 如果原左子节点pl等于null,则说明已经处理完p的所有左子树节点,需要继续处理栈中的节点。如果栈为空,表示已经处理完整棵树,结束循环;否则,从栈中弹出一个节点并赋值给pl。
- 将pl作为p的右子节点。
- 将p更新为新的右子节点pl,并继续循环处理。