给定一个二叉树,原地将它展开为一个单链表。
例如,给定二叉树
1
/
2 5
/ \
3 4 6
将其展开为:
1
2
3
4
5
6
解
二叉树的问题要第一反应过来使用递归求解。
这题参考了评论区大神给出的答案
在还没操作节点右子树前,不能破坏该节点的右子树指向。所以采用后序遍历。
public void flatten(TreeNode root) {
if(root == null) return;
flatten(root.left);
flatten(root.right);
TreeNode tmp = root.right;
root.right = root.left;
root.left = null;
while(root.right != null) root = root.right;
root.right = tmp;
}
网友评论