版权声明:本文为博主原创文章,未经博主允许不得转载。
难度:容易
要求:
将一棵二叉树按照前序遍历拆解成为一个假链表。所谓的假链表是说,用二叉树的 right 指针,来表示链表中的 next 指针。
注意事项
不要忘记将左儿子标记为 null,否则你可能会得到空间溢出或是时间溢出。
样例
1
\
1 2
/ \ \
2 5 => 3
/ \ \ \
3 4 6 4
\
5
\
6
思路:
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
public void flatten(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.empty()) {
TreeNode node = stack.pop();
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
// connect
node.left = null;
if (stack.empty()) {
node.right = null;
} else {
node.right = stack.peek();
}
}
}