Related: LeetCode 430 - Flatten a multilevel linked list
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
http://rangerway.com/way/algorithm-binary-tree-to-linked-list/
LeetCode – Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
1 / \ 2 5 / \ \ 3 4 6
The flattened tree should look like:
http://bangbingsyb.blogspot.com/2014/11/leetcode-flatten-binary-tree-to-linked.html
X. Iterative
What is the time complexity of this solution? I wonder if it is O(nlogn) as we might traverse one root to leaf path per node to get the prenode.
http://buttercola.blogspot.com/2014/08/leetcode-flatten-binary-tree-to-linked.html
X. Left then right, Preorder traverse
https://longwayjade.wordpress.com/2015/04/23/leetcode-recursion-flatten-binary-tree-to-linked-list/
https://www.sigmainfy.com/blog/leetcode-flatten-binary-tree-to-linked-list.html
We can solve this problem in a bottom up approach, that is, do a pre-order traversal, in a recursive way, we get the flatten list for each subtree, by getting the flattend list, we actually only need the head and the tail of that tree, then we append the head of the left list onto the root node, and append the head of the right list onto the tail of the left list. Just be careful when some of the list might be empty. This approach don’t need log N time to find the right most child. So the total time is linear O(N). And the space complexity would be O(h) where h is the height of the tree (i.e., the depth of the recursive calls)
http://bangbingsyb.blogspot.com/2014/11/leetcode-flatten-binary-tree-to-linked.html
假设某节点的左右子树T(root->left)和T(root->right)已经flatten成linked list了:
1
/ \
2 5
\ \
3 6 <- rightTail
\
4 <- leftTail
如何将root、T(root->left)、T(root->right) flatten成一整个linked list?显而易见:
temp = root->right
root->right = root->left
root->left = NULL
leftTail->right = temp
这里需要用到已经flatten的linked list的尾部元素leftTail, rightTail。所以递归返回值应该是生成的整个linked list的尾部。
需注意几个细节
ln 11:只有当左子树存在时才将它插入右子树中
ln 18-20:返回尾部元素时,需要特殊处理 (1) 有右子树的情况,(2) 无右子树但有左子树的情况,(3)左右子树均不存在的情况。
我感觉是在接的过程中是右子树接在了leftTail的下面,因此如果有右子树的话,最后的tail肯定是rightTail,如果没有右子树但是有左子树,tail肯定是leftTail
3) Seems the code gets even more compact. There is another different implementation by using a previous pointer pointing to the previous node in the preorder traversal of the tree and the code actually is easier to understand and the time and space complexity is easier to derive although it is the same as with 2)
http://fisherlei.blogspot.com/2012/12/leetcode-flatten-binary-tree-to-linked.html
1. Line 13~14
刚开始的时候,首先flatten左树,然后处理右树。但是这样会导致处理右树的时候,节点的值已经在处理树的时候被破坏了。比如树为{1,2,3},
1
/ \
2 3
如果先处理左树的话,当执行node->right = lhead的时候,右节点就已经被破坏了,node->right指向了2,而不是3。
1
\
2 (3)
当然,也可以用一个变量在处理左树前,保存右树地址。但是没必要,先处理右树就好了。
2. Line 22~23
该循环是用于将p指针遍历到左树链表的最右节点。第一版时,这个循环是放在if语句以外,这就导致了,不必要的迭代了。比如当输入为{1,#,2}时,这个while循环会导致p指针遍历到右子树的最右节点,这显然是错的。
3. Line 20, 28
不要忘了清空每一个指针,在新的链表中,左指针没必要保留。
https://www.jiuzhang.com/solutions/flatten-binary-tree-to-linked-list/
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/36977/My-short-post-order-traversal-Java-solution-for-share
I would rename "prev" with "nxt" for the purpose of clarification
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
http://rangerway.com/way/algorithm-binary-tree-to-linked-list/
LeetCode – Flatten Binary Tree to Linked List
Given a binary tree, flatten it to a linked list in-place.
1 / \ 2 5 / \ \ 3 4 6
The flattened tree should look like:
1 \ 2 \ 3 \ 4 \ 5 \ 6X.
http://bangbingsyb.blogspot.com/2014/11/leetcode-flatten-binary-tree-to-linked.html
从题目的例子马上发现其实就是preorder transverse整个tree,然后根据这个访问顺序,后访问到的节点成为先访问到的节点的右子节点。那么最不动脑的方法就是preorder transverse的时候把整个节点序列保存在一个vector中。最后再依次连起来。这个解法的空间复杂度包括了递归深度O(log n)和vector的空间O(n),所以总的空间复杂度是O(n)。
void flatten(TreeNode *root) { if(!root) return; vector<TreeNode*> allNodes; preorder(root, allNodes); int n = allNodes.size(); for(int i=0; i<n-1; i++) { allNodes[i]->left = NULL; allNodes[i]->right = allNodes[i+1]; } allNodes[n-1]->left = allNodes[n-1]->right = NULL; } void preorder(TreeNode *root, vector<TreeNode*> &allNodes) { if(!root) return; allNodes.push_back(root); preorder(root->left, allNodes); preorder(root->right, allNodes); }
What is the time complexity of this solution? I wonder if it is O(nlogn) as we might traverse one root to leaf path per node to get the prenode.
http://buttercola.blogspot.com/2014/08/leetcode-flatten-binary-tree-to-linked.html
public
void
flatten(TreeNode root){
if
(root ==
null
)
return
;
TreeNode p = root;
while
(p.left !=
null
|| p.right !=
null
) {
if
(p.left !=
null
) {
TreeNode rChild = p.right;
p.right = p.left;
p.left =
null
;
TreeNode rMost = p.right;
while
(rMost.right !=
null
) {
rMost = rMost.right;
}
rMost.right = rChild;
}
p = p.right;
}
}
5) The final approach cost O(N) time and O(1) space: we directly simulate the process of finding the right most child of the left subtree! See the following code which is accepted:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void flatten(TreeNode *root) {
TreeNode *rightMost = NULL;
TreeNode *tmp = NULL;
while (root) {
if (root->left) {
rightMost = root->left;
while (rightMost->right)
rightMost = rightMost->right;
tmp = root->right;
root->right = root->left;
rightMost->right = tmp;
root->left = NULL;
}
root = root->right;
}
}
https://longwayjade.wordpress.com/2015/04/23/leetcode-recursion-flatten-binary-tree-to-linked-list/
Use pre-oder traversal.
- Define a field, recording the last visited element, so that we don’t lose track of the list when we update references. This field has to be out of the method.
- Base case: if the current node is null, return;
- Reduction: put the current node at lastvisit.right, and the current node becomes the new lastvisit node. Save the current.right node as savedRight, since it’s going to be changed in the next level of recursion. Then, call the method for current.left. After that, call the method for savedRight.
public
TreeNode lastvisit =
null
;
public
void
flatten(TreeNode root) {
if
(root ==
null
)
return
;
TreeNode savedRight = root.right;
// have to save right, since right is going to be changed.
if
(lastvisit !=
null
){
lastvisit.left =
null
;
lastvisit.right = root;
}
lastvisit = root;
flatten(root.left);
flatten(savedRight);
}
We can solve this problem in a bottom up approach, that is, do a pre-order traversal, in a recursive way, we get the flatten list for each subtree, by getting the flattend list, we actually only need the head and the tail of that tree, then we append the head of the left list onto the root node, and append the head of the right list onto the tail of the left list. Just be careful when some of the list might be empty. This approach don’t need log N time to find the right most child. So the total time is linear O(N). And the space complexity would be O(h) where h is the height of the tree (i.e., the depth of the recursive calls)
http://bangbingsyb.blogspot.com/2014/11/leetcode-flatten-binary-tree-to-linked.html
假设某节点的左右子树T(root->left)和T(root->right)已经flatten成linked list了:
1
/ \
2 5
\ \
3 6 <- rightTail
\
4 <- leftTail
如何将root、T(root->left)、T(root->right) flatten成一整个linked list?显而易见:
temp = root->right
root->right = root->left
root->left = NULL
leftTail->right = temp
这里需要用到已经flatten的linked list的尾部元素leftTail, rightTail。所以递归返回值应该是生成的整个linked list的尾部。
需注意几个细节
ln 11:只有当左子树存在时才将它插入右子树中
ln 18-20:返回尾部元素时,需要特殊处理 (1) 有右子树的情况,(2) 无右子树但有左子树的情况,(3)左右子树均不存在的情况。
我感觉是在接的过程中是右子树接在了leftTail的下面,因此如果有右子树的话,最后的tail肯定是rightTail,如果没有右子树但是有左子树,tail肯定是leftTail
void flatten(TreeNode *root) { TreeNode* rightTail = flattenBT(root); } TreeNode* flattenBT(TreeNode* root) { if(!root) return NULL; TreeNode *leftTail = flattenBT(root->left); TreeNode *rightTail = flattenBT(root->right); if(root->left) { TreeNode *temp = root->right; root->right = root->left; root->left = NULL; leftTail->right = temp; } if(rightTail) return rightTail; if(leftTail) return leftTail; return root; }
While the implementation in (1) does not explicitely search the right most child (tail of the flatten linked list). It could actually be done in an explicit way: For each node R, we append the left subtree of R into its right child, and append the right subtree of R onto the right most child of the left subtree of R, we basically follow a DFS order to do this and the tree will be flattened. Every time we need to find the right most subtree in a while loop but from an aggregate analysis, since for each node, the right child is set once, the final time complexity would still be O(N) and the space cost is O(h).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | void flatten(TreeNode *root) { if (NULL == root) return ; TreeNode *rightChild = root->right; root->right = root->left; root->left = NULL; TreeNode *rightMost = root; while (rightMost->right) rightMost = rightMost->right; rightMost->right = rightChild; flatten(root->right); } |
TreeNode *prev = NULL;
void flatten(TreeNode *root) {
if (NULL == root)
return;
TreeNode *l = root->left;
TreeNode *r = root->right;
if (prev) {
prev->right = root;
prev->left = NULL;
}
prev = root;
flatten(l);
flatten(r);
}
4) Further improvement could be done by implementing the algorithm in iterative way. The easiest iterative implementation would be using an explicit stack, please see the “LeetCode Binary Tree Preorder Traversal: Iterative Using Stack” for further reference, and exact implementation could adopted. This approach still does not improve the space cost because the stack depth could still be h which is the height of the tree.
Remarks: Remember to set the left child of each node as NULL, otherwise, the OJ might report run time error
X. Right then lefthttp://fisherlei.blogspot.com/2012/12/leetcode-flatten-binary-tree-to-linked.html
1. Line 13~14
刚开始的时候,首先flatten左树,然后处理右树。但是这样会导致处理右树的时候,节点的值已经在处理树的时候被破坏了。比如树为{1,2,3},
1
/ \
2 3
如果先处理左树的话,当执行node->right = lhead的时候,右节点就已经被破坏了,node->right指向了2,而不是3。
1
\
2 (3)
当然,也可以用一个变量在处理左树前,保存右树地址。但是没必要,先处理右树就好了。
2. Line 22~23
该循环是用于将p指针遍历到左树链表的最右节点。第一版时,这个循环是放在if语句以外,这就导致了,不必要的迭代了。比如当输入为{1,#,2}时,这个while循环会导致p指针遍历到右子树的最右节点,这显然是错的。
3. Line 20, 28
不要忘了清空每一个指针,在新的链表中,左指针没必要保留。
1: void flatten(TreeNode *root) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: if(root == NULL)
5: return;
6: ConvertToLink(root);
7: }
8: TreeNode* ConvertToLink(TreeNode* node)
9: {
10: if(node->left == NULL && node->right == NULL)
11: return node;
12: TreeNode* rHead = NULL;
13: if(node->right != NULL)
14: rHead = ConvertToLink(node->right);
15: TreeNode* p = node;
16: if(node->left!=NULL)
17: {
18: TreeNode* lHead = ConvertToLink(node->left);
19: node->right = lHead;
20: lHead->left = NULL;
21: node->left = NULL;
22: while(p->right!=NULL)
23: p = p->right;
24: }
25: if(rHead != NULL)
26: {
27: p->right = rHead;
28: rHead->left = NULL;
29: }
30: return node;
31: }
X. Post order traversehttps://www.jiuzhang.com/solutions/flatten-binary-tree-to-linked-list/
https://leetcode.com/problems/flatten-binary-tree-to-linked-list/discuss/36977/My-short-post-order-traversal-Java-solution-for-share
I would rename "prev" with "nxt" for the purpose of clarification
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;
}
public void flatten(TreeNode root) {
root = helper(root, null);
}
// helper function takes in the previous head, do the flattening and returns the head of the flatten binary tree
private TreeNode helper(TreeNode root, TreeNode prev) {
if (root == null) {
return prev;
}
prev = helper(root.right, prev);
prev = helper(root.left, prev);
root.right = prev;
root.left = null;
prev = root;
return root;
}
X.
根据展开后形成的链表的顺序分析出是使用先序遍历,那么只要是数的遍历就有递归和非递归的两种方法来求解,这里我们也用两种方法来求解。首先来看递归版本的,思路是先利用DFS的思路找到最左子节点,然后回到其父节点,把其父节点和右子节点断开,将原左子结点连上父节点的右子节点上,然后再把原右子节点连到新右子节点的右子节点上,然后再回到上一父节点做相同操作
Pre-Order Recursive Version:
维护先序遍历的前一个结点pre,然后每次把pre的左结点置空,右结点设为当前结点。这里需要注意的一个问题就是我们要先把右子结点保存一下,以便等会可以进行递归,否则有可能当前结点的右结点会被覆盖,后面就取不到了
http://rangerway.com/way/algorithm-binary-tree-to-linked-list/
http://www.jiuzhang.com/solutions/flatten-binary-tree-to-linked-list/
void flattenPreorder(TreeNode root, TreeNode[] prev) {
if (root == null) return;
TreeNode rightBranch = root.right;
root.left = null;
if (prev[0] != null) {
prev[0].right = root;
}
prev[0] = root;
flattenPreorder(root.left, prev);
flattenPreorder(rightBranch, prev);
}
X. Stack Pre-Oder traversal:
http://gongxuns.blogspot.com/2012/12/leetcode-flatten-binary-tree-to-linked.html
DFS prev pointer.
O(nlogn)
The flatten procedure is like: cut the left child and set to right, the right child is then linked to somewhere behind the left child. Where should it be then? Actually the right child should be linked to the most-right node of the left node. So the algorithm is as follows:
(1) store the right child (we call R)
(2) find the right-most node of left child
(3) set R as the right-most node's right child.
(4) set left child as the right child
(5) set the left child NULL
(6) set current node to current node's right child.
(7) iterate these steps until all node are flattened.
对root的左子树进行处理,将左子树的根节点和左子树的右子树插入右子树中
http://rangerway.com/way/algorithm-binary-tree-to-linked-list/
http://fisherlei.blogspot.com/2012/12/leetcode-flatten-binary-tree-to-linked.html
Inorder version
TreeNode flattenInorder(TreeNode root) {
TreeNode[] prev = new TreeNode[1];
TreeNode[] head = new TreeNode[1];
flattenInorder(root, prev, head);
return head[0];
}
void flattenInorder(TreeNode root, TreeNode[] prev, TreeNode[] head) {
if (root == null) return;
flattenInorder(root.left, prev, head);
root.left = null;
if (prev[0] != null) {
prev[0].right = root;
}
prev[0] = root;
if (head[0] == null) {
head[0] = root;
}
flattenInorder(root.right, prev, head);
}
PreOder
if (root == null) return;
TreeNode rightBranch = root.right;
root.left = null;
if (prev[0] != null) {
prev[0].right = root;
}
prev[0] = root;
flattenPreorder(root.left, prev);
flattenPreorder(rightBranch, prev);
}
Post-Order to List.
void flattenPostorder(TreeNode root, TreeNode[] prev, TreeNode[] head) {
if (root == null) return;
flattenPostorder(root.left, prev, head);
if (head[0] == null) {
head[0] = root;
}
flattenPostorder(root.right, prev, head);
root.left = null;
root.right = null;
if (prev[0] != null) {
prev[0].right = root;
}
prev[0] = root;
}
The iteration traverse of Binary Tree is commonly implemented with an assistant Stack. But in this quesiton, we are required to use constant space, so we should take advantage of the left/right pointers.
Pre-Order
void flattenInorder(TreeNode root) {
while (root != null) {
if (root.left != null) {
TreeNode prev = root.left;
while (prev.right != null) {
prev = prev.right;
}
prev.right = root.right;
root.right = root.left;
root.left = null;
}
root = root.right;
}
}
TreeNode flattenInorder(TreeNode root) {
TreeNode head = null;
TreeNode last = null;
while (root != null) {
if (root.left != null) {
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
pre.right = root;
pre = pre.right;
root = root.left;
pre.left = null;
if (last != null) {
last.right = root;
}
} else {
if (head == null) head = root;
last = root;
root = root.right;
}
}
return head;
}
此题还可以延伸到用中序,后序,层序的遍历顺序来展开原二叉树,分别又有其对应的递归和非递归的方法,有兴趣的童鞋可以自行实现
flatten left subtree
flatten right subtree
concatenate root -> left flatten subtree -> right flatten subtree
public void flatten(TreeNode root) {
if(root == null)
return;
flatten(root.left);
flatten(root.right);
// save current right for concatination
TreeNode right = root.right;
if(root.left != null) {
// step 1: concatinate root with left flatten subtree
root.right = root.left;
root.left = null; // set left to null
// step 2: move to the end of new added flatten subtree
while(root.right != null)
root = root.right;
// step 3: contatinate left flatten subtree with flatten right subtree
root.right = right;
}
}
What's the time complexity? Is this O(nlogn)?
I think that each time when there is a "branch", we need to traverse the left chid of the root, which means that the time that every node will be visited depends on how many branches there are. Since there are logn branches at most, I think the worst case is O(nlogn).
I think that each time when there is a "branch", we need to traverse the left chid of the root, which means that the time that every node will be visited depends on how many branches there are. Since there are logn branches at most, I think the worst case is O(nlogn).
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)
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;
}
Pre-Order Recursive Version:
维护先序遍历的前一个结点pre,然后每次把pre的左结点置空,右结点设为当前结点。这里需要注意的一个问题就是我们要先把右子结点保存一下,以便等会可以进行递归,否则有可能当前结点的右结点会被覆盖,后面就取不到了
http://rangerway.com/way/algorithm-binary-tree-to-linked-list/
http://www.jiuzhang.com/solutions/flatten-binary-tree-to-linked-list/
void flattenPreorder(TreeNode root, TreeNode[] prev) {
if (root == null) return;
TreeNode rightBranch = root.right;
root.left = null;
if (prev[0] != null) {
prev[0].right = root;
}
prev[0] = root;
flattenPreorder(root.left, prev);
flattenPreorder(rightBranch, prev);
}
private TreeNode lastNode = null; public void flatten(TreeNode root) { if (root == null) { return; } if (lastNode != null) { lastNode.left = null; lastNode.right = root; } lastNode = root; TreeNode right = root.right; flatten(root.left); flatten(right); }http://www.acmerblog.com/leetcode-solution-flatten-binary-tree-to-linked-list-6321.html
05 | void flatten(TreeNode *root) { |
06 | if (root == nullptr) return ; // 终止条件 |
07 |
08 | flatten(root->left); |
09 | flatten(root->right); |
10 |
11 | if (nullptr == root->left) return ; |
12 |
13 | // 三方合并,将左子树所形成的链表插入到root和root->right之间 |
14 | TreeNode *p = root->left; |
15 | while (p->right) p = p->right; //寻找左链表最后一个节点 |
16 | p->right = root->right; |
17 | root->right = root->left; |
18 | root->left = nullptr; |
19 | } |
X. Stack Pre-Oder traversal:
Go down through the left, when right is not null, push right to stack. public void flatten(TreeNode root) { Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode p = root; while(p != null || !stack.empty()){ if(p.right != null){ stack.push(p.right); } if(p.left != null){ p.right = p.left; p.left = null; }else if(!stack.empty()){ TreeNode temp = stack.pop(); p.right=temp; } p = p.right; } }
DFS prev pointer.
public void flatten(TreeNode root) { Stack<TreeNode> toVisit = new Stack<TreeNode>(); if(root==null) return; toVisit.push(root); TreeNode prev = null; while(!toVisit.isEmpty()){ TreeNode cur = toVisit.pop(); if(cur.right!=null) toVisit.push(cur.right); if(cur.left!=null) toVisit.push(cur.left); if(prev!=null){ prev.left=null; prev.right = cur; } prev=cur; }http://yucoding.blogspot.com/2013/01/leetcode-question-30-flatten-binary.html
O(nlogn)
The flatten procedure is like: cut the left child and set to right, the right child is then linked to somewhere behind the left child. Where should it be then? Actually the right child should be linked to the most-right node of the left node. So the algorithm is as follows:
(1) store the right child (we call R)
(2) find the right-most node of left child
(3) set R as the right-most node's right child.
(4) set left child as the right child
(5) set the left child NULL
(6) set current node to current node's right child.
(7) iterate these steps until all node are flattened.
void
flatten(TreeNode *root) {
while
(root){
if
(root->left){
TreeNode* pre=root->left;
while
(pre->right){pre = pre->right;}
pre->right = root->right;
root->right = root->left;
root->left = NULL;
}
root=root->right;
}
}
接下来对节点2进行处理,同样将2的左子树插入右子树中
public void flatten(TreeNode root) { 4 if(root == null){ 5 return; 6 } 8 if(root.left != null){ 9 TreeNode rightNode = root.right; 10 TreeNode leftNode = root.left; 11 root.left = null; 12 root.right = leftNode; 13 TreeNode p = leftNode; 14 while(p.right != null){ 15 p = p.right; 16 } 17 p.right = rightNode; 18 } 19 flatten(root.right); 20 }
http://blog.csdn.net/perfect8886/article/details/20000083
1 \ 2 / \ 3 4 \ 5 \ 6
还有种非递归的写法,没有借助栈就实现了按先序遍历顺序展平,在构造过程中,只要树中有多出来的分叉(左子树),就嫁接到根节点和右子树之间,具体参见解法2。
http://codesays.com/2014/solution-to-flatten-binary-tree-to-linked-list-by-leetcode/
- public void flatten(TreeNode root) {
- while (root != null) {
- if (root.left != null) {
- TreeNode p = root.left;
- while (p.right != null) {
- p = p.right;
- }
- p.right = root.right;
- root.right = root.left;
- root.left = null;
- }
- root = root.right;
- }
- }
http://rangerway.com/way/algorithm-binary-tree-to-linked-list/
http://fisherlei.blogspot.com/2012/12/leetcode-flatten-binary-tree-to-linked.html
Inorder version
TreeNode flattenInorder(TreeNode root) {
TreeNode[] prev = new TreeNode[1];
TreeNode[] head = new TreeNode[1];
flattenInorder(root, prev, head);
return head[0];
}
void flattenInorder(TreeNode root, TreeNode[] prev, TreeNode[] head) {
if (root == null) return;
flattenInorder(root.left, prev, head);
root.left = null;
if (prev[0] != null) {
prev[0].right = root;
}
prev[0] = root;
if (head[0] == null) {
head[0] = root;
}
flattenInorder(root.right, prev, head);
}
PreOder
- As the root of BT is the head of LL, we do not need to set head pointer.
- As the right pointer of each node will be set before recusion called on rightBranch, so we need to set a variable to mark rightBranch in every recursion.
if (root == null) return;
TreeNode rightBranch = root.right;
root.left = null;
if (prev[0] != null) {
prev[0].right = root;
}
prev[0] = root;
flattenPreorder(root.left, prev);
flattenPreorder(rightBranch, prev);
}
Post-Order to List.
void flattenPostorder(TreeNode root, TreeNode[] prev, TreeNode[] head) {
if (root == null) return;
flattenPostorder(root.left, prev, head);
if (head[0] == null) {
head[0] = root;
}
flattenPostorder(root.right, prev, head);
root.left = null;
root.right = null;
if (prev[0] != null) {
prev[0].right = root;
}
prev[0] = root;
}
The iteration traverse of Binary Tree is commonly implemented with an assistant Stack
void flattenInorder(TreeNode root) {
while (root != null) {
if (root.left != null) {
TreeNode prev = root.left;
while (prev.right != null) {
prev = prev.right;
}
prev.right = root.right;
root.right = root.left;
root.left = null;
}
root = root.right;
}
}
TreeNode flattenInorder(TreeNode root) {
TreeNode head = null;
TreeNode last = null;
while (root != null) {
if (root.left != null) {
TreeNode pre = root.left;
while (pre.right != null) {
pre = pre.right;
}
pre.right = root;
pre = pre.right;
root = root.left;
pre.left = null;
if (last != null) {
last.right = root;
}
} else {
if (head == null) head = root;
last = root;
root = root.right;
}
}
return head;
}
此题还可以延伸到用中序,后序,层序的遍历顺序来展开原二叉树,分别又有其对应的递归和非递归的方法,有兴趣的童鞋可以自行实现