FlattenBinaryTreeToLinkedList [source code]
public class FlattenBinaryTreeToLinkedList {
static
/******************************************************************************/
class Solution {
public void flatten(TreeNode root) {
helper (root);
}
TreeNode helper (TreeNode root) {
if (root == null)
return null;
TreeNode left_max = helper (root.left);
if (left_max != null) {
left_max.right = root.right;
root.right = root.left;
root.left = null;
}
TreeNode right_max = helper (root.right);
return right_max == null ? root : right_max;
}
}
/******************************************************************************/
public static void main(String[] args) {
FlattenBinaryTreeToLinkedList.Solution tester = new FlattenBinaryTreeToLinkedList.Solution();
}
}
这题的难点应该是这个InPlace; 最后要你返回的不是一个专门的单独的ListNode, 而是直接在原来的TreeNode里面修改;
刚开始一个简单的思路, 就是直接DFS来从左往右走, 然后在走的过程中, 完成一个PreOrder顺序的append, 比如维护一个prev; 但是这个思路有一个问题, 你在走PreOrder的过程中如果就直接开始修改的话, 最后整个tree就被修改了, 比如你走到2的时候把2放到了1.right, 那么你5怎么办?
所以这里涉及到一个顺序的问题; 好像顺序最好是倒过来做; 以前说过, 在类似LinkedList问题当中, 需要倒序的时候, 一个思路就是直接用recursion, 这里好像可以借鉴这个思路;
然后很自然的就想到了returned recursion的思路:
看到这个图, 思路应该就很清楚了; 一个subtree的recursion好像应该返回当前subtree的最大值, 然后root level decision就是, root.right = root.left, left_max.right = root.right这样的思路; 然后root把right_max返回上去;
除了给的这个例子, 你还应该考虑:
1
/ \
2 5
/ \
3 6
这个跟上一个tree的处理有什么不同;
最后还是按时做完了, 看起来感觉逻辑其实也挺好的, 但是速度很差, 只有24ms (1%), 不知道哪里有问题;
没有editorial;
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;
}
这个思路还是很类似的, 不过他不是依赖返回值传递, 而是直接用一个全局变量来保存这个一个subtree的最右端结点;
大概画了一下:
好像跟我的思路并不是一样的; 比如说, 我的其实是一个InOrder的做法, 但是他这里这个明显是一个PostOrder的做法;
你仔细看他这个例子, 他这个并不是一个单纯的returned recursion的思路, 而是一个就是准确的完成倒序的做法; 用一个reversed(先right然后left)的PostOrder, 完成一个从最低端开始循环的过程; 这个算法开发的思路估计就是直接从比较简单的类似1 2 3这样的tree开始思考, 思考出来大概的root level decision的逻辑之后, 再看看怎么拓展到比如高度+1的tree上面去;
然后这个是他避免global的做法:
This is really brilliant! But flatten() would be unreusable if prev is set to a field. Here’s another way of implementing the same idea.
public void flatten(TreeNode root) {
flatten(root,null);
}
private TreeNode flatten(TreeNode root, TreeNode pre) {
if(root==null) return pre;
pre=flatten(root.right,pre);
pre=flatten(root.left,pre);
root.right=pre;
root.left=null;
pre=root;
return pre;
}
Great idea! Just for clarify, this is not post order. this is ‘reversed’ preorder.
我认为叫做reversed PostOrder更加合适, 不过他这个叫法, 实际上更加契合这个题目的意思, 因为这个题目最后的目的就是完成一个PreOrder的traversal, 那么他这里倒序之后, 自然做的就是reversed的PreOrder;
Lemme try to explain @tusizi 's idea a little bit, based on his code snippet.
As you can see, the problem asks for a linkedlist-alike result. To build a linked list recursively, let’s say we have reached recursion depth d, we need to set the current node cur 's next attribute as the return value of recursion call d+1. And we return cur, which will be used in d-1 recursion. Pretty much like that.
Similarly, for this problem, we also need to find the current node’s next node. For this problem, we use TreeNode prev to hold the next node (I must say, I’d prefer it is named as next or something.) The difference from above is that, instead of returning the next node, @tusizi uses a global variable to maintain the next node. The reason will be stated in the following. But I have point out, I agree with @cifer-lee , it remains to be discussed if it is a good way for doing so, but for now let’s just assume it is. In the following, I will use linked list or tree, head or root, right or next, interchangeably.
Let’s inspect the execution process of @tusizi 's code snippet a little bit.
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;
}
After flatten(root.right), we have processed the right branch of the current node, and the current prev is the head of root of the right branch. For now, we want to know which node is the precedent node of prev, and we will set this particular node’s next attribute as prev. As per the problem, this particular node is actually the rightmost node of the left branch.
Next, let’s say why we can actually get it. So now we go to the next line, which is flatten(root.left). When we go deeper and deeper in the recursion, we are actually going right because we go right before we go left. A small remark here, the traversal order of the code snippet is actually right->left->cur, not post-order, more like reversed post order if you like. As we are going right, we will stop when we cannot go right furthermore. Then we set right or next attribute of the current node as prev, which is exactly what we want.
Now let’s go back to the original function call layer, we have done flatten(root.right) and flatten(root.right). The remaining is easy, we set the root node’s next node as prev, which is the head of the left branch. Done!
A little more comment on why we cannot return the current node like what we do in linked list for this solution. The short answer is that tree is non-liner. The more verbose answer is that we want to connect the rightmost node on the left branch to the leftmost node on the right branch, this is something that we cannot achieve in the current layer directly. If we insist on returning value, we may need to traverse the left branch on our own, and then do the same connection stuff. This is what a lot other solutions are doing, like this one hanzhou87’s solution. My solution is to return the end node of left branch directly.
大概的解释的意思是能理解的, 不过实际上看了代码之后这个算法本身并不是很难理解; 只能说这个算法的思路其实更加的imperative, 就是一个很严谨的分析PostOrder(没错, 实际上这个算法本身的行为模式就是PostOrder, 对应的结果就是, 对于一个subtree, 第一个被执行的总是最右下角的node)然后得到一个利用这个执行顺序来做事的方式;
这个是一个跟我类似的思路:
You go right first and I go left first. lol.
public class Solution {
private static TreeNode pointer = null;
public void flatten(TreeNode root) {
if(root == null)
return;
if(pointer != null)
pointer.right = root;
pointer = root;
TreeNode right = root.right;
flatten(root.left);
root.left = null;
flatten(right);
}
}
The concise solution posted above does compel us to further investigate that sub-structure to this problem.
Below solution is similar, but it does actually involve a preorder traversal, so might be a bit easier to grasp. Flattening of a tree basically involves three steps:
Set present right sub-tree as the right sub-tree of the last visited node (prev) on the left.
Set present left sub-tree as the new right sub-tree.
Set left sub-tree to NULL.
Now recursively repeat the above three steps:
void rflatten(struct TreeNode root, struct TreeNode *prev)
{
// Return if the root is invalid
if (!root) return;
*prev = root; // tracks the last visited node on the left
rflatten(root->left, prev);
(*prev)->right = root->right; // Step 1
root->right = (root->left) ? root->left : root->right; // Step 2
root->left = NULL; // Step 3
rflatten((*prev)->right, prev);
}
也是类似的;
---
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/37010/Share-my-simple-NON-recursive-solution-O(1)-space-complexity!
```c++
class Solution {
public:
void flatten(TreeNode *root) {
TreeNode*now = root;
while (now)
{
if(now->left)
{
//Find current node's prenode that links to current node's right subtree
TreeNode* pre = now->left;
while(pre->right)
{
pre = pre->right;
}
pre->right = now->right;
//Use current node's left subtree to replace its right subtree(original right
//subtree is already linked by current node's prenode
now->right = now->left;
now->left = NULL;
}
now = now->right;
}
}
};
还是用上面的那个简单的例子, 大概看懂了, 这个是一个很类似Morris traversal的做法; 最关键的一步是最后一行的now = now->right;.
Time is O(n), here’s why:
You’re moving now over all nodes and for each one potentially dive down deep into its left subtree, so one might think it’s more than O(n) time. But… a long path down the left subtree immediately pays off, as you then insert that entire path into the “right border” of the whole tree, where now will walk over it once more but pre will never have to walk over it again.
To put it differently: Every node is visited by now exactly once and by pre at most once, and the runtime is proportional to the number of steps taken by now and pre, so O(n) overall.
我自己给一个解释:
这个过程还是好理解的; 然后这个算法的intuition:
public void flatten(TreeNode root) {
if (root == null) return;
TreeNode left = root.left;
TreeNode right = root.right;
root.left = null;
flatten(left);
flatten(right);
root.right = left;
TreeNode cur = root;
while (cur.right != null) cur = cur.right;
cur.right = right;
}
This solution is based on recursion. We simply flatten left and right subtree and paste each sublist to the right child of the root. (don’t forget to set left child to null)
比较蠢, 还要专门走一趟来找到left max;
但是有人提出:
Complexity is still O(n). You never visit a node more than twice if you think about it.
想了一下, 好像还真是这么一回事;
这个算法的trace实际上跟上面那个iterative的做法是很相似的;
public void Flatten(TreeNode root) {
solve(root, null);
}
TreeNode solve(TreeNode root, TreeNode last) {
if(root == null) return last;
root.right = solve(root.left, solve(root.right, last));
root.left = null;
return root;
}
这个跟第一个解法实际上是类似的, 是一个倒序build的过程; 只不过代码组织上更加简练;
it is DFS so u need a stack. Dont forget to set the left child to null, or u’ll get TLE. (tricky!)
```java
public void flatten(TreeNode root) {
if (root == null) return;
Stack
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; // dont forget this!!
}
}
大概理解了一下, 这个算法的正确性肯定是没有问题的, 就是不太理解背后的intuition;
<img src="https://www.dropbox.com/s/hs8liseuuzsps0c/Screenshot%202018-02-20%2012.09.48.png?raw=1" width="400">
可以看到, 左边的这个实际上是我画错了; 在画这个trace的过程中用红圈来代表in Stack, 跑完这些圈也就都擦掉了;
他这个算法的核心主干就是一个标准的Stack PreOrder的写法; 我刚开始也是有过这个思路的, 就是怕这个adapatation没有想象当中的这么简单;
结果后面看看他这个结果的trace, 好像实际上就是在走PreOrder的过程当中, 直接一个连一个就行了; 为什么recursive PreOrder做不到的, 这里这个可以做到? 因为这里有一个Stack来帮忙维护顺序: 虽然原来的tree被修改了, 我们的node还是按照正确的顺序被维护在Stack里面, 所以照样可以正常traversal;
当然底下很多人其实认为这个算法就不算是InPlace了; 说实话这个思路是有点降低难度了, 有了Stack之后就不担心InPlace modify带来的危险, 而这个InPlace **modify**本身就是这个题目的考点;
不过这个算法本身还是有学习意义的;
---
submission基本波动, 第一梯队是老submission;
---
### Problem Description
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1
/ \
2 5
/ \ \
3 4 6
The flattened tree should look like:
1
\
2
\
3
\
4
\
5
\
6
``` click to show hints.
Hints:
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.
Difficulty:Medium
Total Accepted:156.2K
Total Submissions:430.5K
Contributor:LeetCode
Companies
microsoft
Related Topics
treedepth-first search