LeetCode 114 : 二叉树展开为链表
描述:
给你二叉树的根结点 root ,请你将它展开为一个单链表:
list
当中list
中的元素,让i
下标节点的左子树为空,右子树指向i+1
下标的节点.class Solution {
public void flatten(TreeNode root) {
List<TreeNode> list = new ArrayList<TreeNode>();
preorderTraversal(root, list);
for (int i = 0; i < list.size() - 1; i++) {
list.get(i).left = null;
list.get(i).right = list.get(i+1);
}
}
public void preorderTraversal(TreeNode root, List<TreeNode> list) {
if (root == null) return;
list.add(root);
preorderTraversal(root.left, list);
preorderTraversal(root.right, list);
}
}
list
当中.循环该节点的左子树,直到为空停止循环.class Solution {
public void flatten(TreeNode root) {
if(root == null) return;
Stack<TreeNode> stack = new Stack<>();
List<TreeNode> list = new ArrayList<>();
TreeNode cur = root;
//cur 不为空 或 栈 不为空 进入循环
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);//cur不为空就入栈
list.add(cur);//入栈的同时插入到list中
cur = cur.left;//根->左的顺序
}
TreeNode top = stack.pop();
cur = top.right;//根->左 结束之后 就开始 右
}
//遍历list
for (int i = 0; i < list.size() - 1; i++) {
list.get(i).left = null;
list.get(i).right = list.get(i+1);
}
}
}
cur
指向root
.root
的左子树不为空,引用一个curNext
指向root.left
;pre
指向curNext
,循环直到pre.right = null
,如果pre.right != null
,让pre = pre.right
. 如果循环结束,pre.right == null
. 让pre.right = cur. right
.cur.left = null
, cur.right = curNext
; cur = cur.right
;class Solution {
public void flatten(TreeNode root) {
if(root == null) return;
TreeNode cur = root;
TreeNode curNext = null;
while (cur != null){
if(cur.left != null){
curNext = cur.left;
TreeNode pre = curNext;
//让pre指向左子树的最右节点
while (pre.right != null){
pre = pre.right;
}
//让左子树最右节点和右子树链接
pre.right = cur.right;
//让根节点的左边断开
cur.left = null;
//让根节点的右子树连接左子树
cur.right = curNext;
}
cur = cur.right;
}
}
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/wwzzzzzzzzzzzzz/article/details/122172287
内容来源于网络,如有侵权,请联系作者删除!