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
关于二叉树的题目,最直接最简单的方法就是采用递归,因为二叉树具有天然的递归结构,实际上二叉树的定义就是用递归的思想来定义的:一个节点的左右子树任然是一个二叉树。
public void flatten(TreeNode root) {
if (root ==null||(root.right==null&&root.left==null)) return;
flatten(root.left);
flatten(root.right);
TreeNode temp = root.right;
root.right = root.left;
root.left = null;
TreeNode cur = root;
while (cur.right!=null){
cur =cur.right;
}
cur.right = temp;
}
解法一的思路比较简单,但是要让左子树做flatten后的最后一个节点指向右子树做flatten操作后的第一个节点
,如何得到左子树做flatten后的最后一个节点呢?这就需要一个循环,上述代码中的:
TreeNode cur = root;
while (cur.right!=null){
cur = cur.right;
}
让cur记录左子树做flatten后的最后一个节点,这样增加了算法的复杂性,效率不是很高。
思路:与解法一中的递归思路不一样,我们可以没每找到理论结果中的最后一个节点,再找理论结果中的倒数第二个节点,再倒数第三个………,依次类推,最后找到的是root节点。将写出以下的算法:
private TreeNode prev = null;
public void flatten(TreeNode root) {
if (root == null)
return;
flatten(root.right);
flatten(root.left);
root.right = prev ;
root.left = null;
prev = root;
}
注意:这里的prev是一个全局变量,prev存的是上一次递归的root的结果。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。