Given a binary tree, flatten it to a linked list in-place.
For example,
Given
1 / \ 2 5 / \ \ 3 4 6The flattened tree should look like:
1 \ 2 \ 3 \ 4 \ 5 \ 6A:
就是,只用right指针来指向下一个。
-----------------recursively 调用----------------------
public class FlattenBinaryTreeToLinkedList { public void flatten(TreeNode root) { flatten(null,root); } private TreeNode helper(TreeNode preNode, TreeNode root ){ // use a preNode to record the the last added node in if(root == null) return null; if(preNode != null){ preNode.left = null; preNode.right = root; } preNode = root; TreeNode tmpRight = root.right; // coz root.right might be changed // add left if(root.left != null) preNode = helper(preNode, root.left); if(tmpRight != null) preNode = helper(preNode,tmpRight); return preNode; } }----------------------把通过preNode的传递的参数,换成类变量。 不提倡,软件工程方面差-----------
public class Solution { TreeNode preNode = null; public void flatten(TreeNode root) { if(root == null) return; if(preNode !=null) preNode.right = root; preNode = root; TreeNode tmpRight = root.right; if(root.left !=null){ flatten(root.left); root.left = null; } if(tmpRight!= null) flatten(tmpRight); } }*****************每次返回最后一个node,并接上 尾巴即可 ******************
public class Solution { public void flatten(TreeNode root) { helper(root); } private TreeNode helper(TreeNode root){ // each return the right most node if(root == null) return null; TreeNode tail = root, r = root.right, l = root.left; root.left = null; if( l != null ){ root.right = l; tail = helper(l); } if( r != null ){ tail.right = r; tail = helper(r); } return tail; } }
--------------------用一个stack 保存前序遍历的结果,并调整。
public class FlattenBinaryTreeToLinkedList2 { public void flatten(TreeNode root) { if (root == null) return; // use a stack to remember to be vistied right child // following two ways to declare a stack works. // LinkedList<TreeNode> stack = new LinkedList<TreeNode>(); Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); TreeNode preNode = null; while (!stack.isEmpty()) { TreeNode curNode = stack.pop(); if (preNode != null) { preNode.left = null; preNode.right = curNode; } if (curNode.right != null) stack.push(curNode.right); if (curNode.left != null) stack.push(curNode.left); preNode = curNode; } } }
Mistakes:
1: 开始,没有加JustedAddedNode.left == null
如果不加的话, 其节点总是保留着, 是不对的。呵呵, 第二遍的时候,又犯了这个错误!!!
2: 用stack存储的话,记得先把左右两边push进去,再更改current node的左右值。
No comments:
Post a Comment