首页 > 代码库 > Flatten Binary Tree to Linked List leetcode java
Flatten Binary Tree to Linked List leetcode java
题目:
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 6
题解:
如hint所给出,这道题就是使用先序遍历,遍历到的值作为新的右孩子存起来,左孩子变为空。
注意的是,因为右孩子会更新,所以为了递归右子树,要在更新之前提前保存右孩子。
整个程序需要维护一个全局变量,保存当前所遍历的节点。
代码如下:
1 TreeNode lastvisited = null;
2 public void flatten(TreeNode root) {
3 if(root == null)
4 return;
5
6 TreeNode realright = root.right;
7 if(lastvisited != null){
8 lastvisited.left = null;
9 lastvisited.right = root;
10 }
11
12 lastvisited = root;
13 flatten(root.left);
14 flatten(realright);
15 }
2 public void flatten(TreeNode root) {
3 if(root == null)
4 return;
5
6 TreeNode realright = root.right;
7 if(lastvisited != null){
8 lastvisited.left = null;
9 lastvisited.right = root;
10 }
11
12 lastvisited = root;
13 flatten(root.left);
14 flatten(realright);
15 }
Reference:http://blog.csdn.net/perfect8886/article/details/20000083
此题还有不用递归方法解决的方法,那就是使用栈。
对整棵树一直向右子树方向遍历。当遍历的节点有右孩子时,就将其入栈。有左孩子时,将其更新为当前节点的右孩子,左孩子置空。当左孩子为空时而栈不空时,
就弹出栈,作为右孩子。代码如下:
1 public void flatten(TreeNode root) {
2 Stack<TreeNode> stack = new Stack<TreeNode>();
3 TreeNode p = root;
4
5 while(p != null || !stack.empty()){
6
7 if(p.right != null){
8 stack.push(p.right);
9 }
10
11 if(p.left != null){
12 p.right = p.left;
13 p.left = null;
14 }else if(!stack.empty()){
15 TreeNode temp = stack.pop();
16 p.right=temp;
17 }
18
19 p = p.right;
20 }
21 }
2 Stack<TreeNode> stack = new Stack<TreeNode>();
3 TreeNode p = root;
4
5 while(p != null || !stack.empty()){
6
7 if(p.right != null){
8 stack.push(p.right);
9 }
10
11 if(p.left != null){
12 p.right = p.left;
13 p.left = null;
14 }else if(!stack.empty()){
15 TreeNode temp = stack.pop();
16 p.right=temp;
17 }
18
19 p = p.right;
20 }
21 }
Reference: //http://www.programcreek.com/2013/01/leetcode-flatten-binary-tree-to-linked-list/
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。