首页 > 代码库 > [Leetcode][JAVA] Flatten Binary Tree to Linked List
[Leetcode][JAVA] Flatten Binary Tree to Linked List
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 6Hints:
If you notice carefully in the flattened tree, each node‘s right child points to the next node of a pre-order traversal.
这个提示反而让人联想到用栈或者递归去做。然而严格意义上这样做使用了额外空间。discuss里面有人提供了很好的非递归算法，似乎是Morris遍历的应用：
记录一个节点cur,起始为根节点。对于这个cur节点，如果有左子树，做两件事：
1. 把左子树的最右节点的right指针指向cur的右子树。
2. cur的right指针指向cur的左子树，cur的left指针指向null.
如果没有左子树就不做这两件事。
这样就算扁平化了一个节点。接着把cur挪到cur的右子树根节点去（原来的左子树根节点），然后继续重复这两件事，直到cur为null.
代码如下：
1 public void flatten(TreeNode root) { 2 TreeNode cur = root; 3 while(cur!=null) { 4 if(cur.left!=null) { 5 TreeNode leftRight = cur.left; 6 while(leftRight.right!=null) 7 leftRight = leftRight.right; 8 leftRight.right = cur.right; 9 cur.right = cur.left;10 cur.left = null;11 }12 cur = cur.right;13 }14 }
附：使用栈实现的前序遍历做法：
1 public void flatten(TreeNode root) { 2 Stack<TreeNode> st = new Stack<TreeNode>(); 3 st.push(root); 4 if(root==null) 5 return; 6 while(!st.isEmpty()) 7 { 8 TreeNode temp = st.pop(); 9 if(temp.right!=null)10 st.push(temp.right);11 if(temp.left!=null)12 st.push(temp.left);13 temp.left=null;14 if(!st.isEmpty())15 temp.right = st.peek();16 else17 temp.right = null;18 }19 }
[Leetcode][JAVA] Flatten Binary Tree to Linked List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。