Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:...
Given a binary tree, flatten it to a linked list in-place.
For example, given the following tree:
1
/ \\
2 5
/ \\ \\
3 4 6
The flattened tree should look like:
1
\\
2
\\
3
\\
4
\\
5
\\
6
方法1：（利用栈的形式）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public void flatten(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stk = new Stack<TreeNode>();
stk.push(root);
while (!stk.isEmpty()){
TreeNode curr = stk.pop();
if (curr.right!=null)
stk.push(curr.right);
if (curr.left!=null)
stk.push(curr.left);
if (!stk.isEmpty())
curr.right = stk.peek();
// 它的左子树要为空
curr.left = null;
}
}
}
时间复杂度：O(n)
空间复杂度：O(1)
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
上一篇：<link>标签实现预加载功能 下一篇：基于vue.js的原生日历
