首页 > 代码库 > [LeetCode#114]Flatten Binary Tree to Linked List
[LeetCode#114]Flatten Binary Tree to Linked List
The problem:
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
A wrong solution :
public class Solution { public void flatten(TreeNode root) { if (root == null) return; ArrayList<TreeNode> pre = new ArrayList<TreeNode>(); TreeNode dummy = new TreeNode(0); //use a dummy node for wirtting invariant pre.add(dummy); helper(root, pre); } private void helper(TreeNode cur, ArrayList<TreeNode> pre) { if (cur == null) return; TreeNode pre_node = pre.get(0); pre_node.left = null; pre_node.right = cur; pre.set(0, cur); helper(cur.left, pre);//this could change the right child value to cur, before reaching the next nextstatement. helper(cur.right, pre); }}
An analyssis for the error:
This question could be easily solved by using recursion, but when writing the program, we might introduce a big pitfall.Let‘s firstly consdiering the following buggy code: private void helper(TreeNode cur, ArrayList<TreeNode> pre) { if (cur == null) return; TreeNode pre_node = pre.get(0); pre_node.left = null; pre_node.right = cur; pre.set(0, cur); helper(cur.left, pre); helper(cur.right, pre); } The buggy code looks extraordinarily fine, if we thinking it from the perspective of non-recursion program.A big pitfall:1 helper(cur.left, pre); //we call the recursive function2 helper(cur.right, pre);the statement 1 would change the value of cur node.(even it does not change current pointer)in : 1. pre_node.left = null;2. pre_node.right = cur;This would lead to a infinite loop, thus result in stack overflow.The classic way to solve this problem is to keep a copy of left child and right child‘s pointer copy. TreeNode left = cur.left; TreeNode right = cur.right;Thus any recursion in the lower level would not affect current level‘s value.(it‘s very important!!!)
My accepted solution:
public class Solution { public void flatten(TreeNode root) { if (root == null) return; ArrayList<TreeNode> pre = new ArrayList<TreeNode>(); TreeNode dummy = new TreeNode(0); //use a dummy node for wirtting invariant pre.add(dummy); helper(root, pre); } private void helper(TreeNode cur, ArrayList<TreeNode> pre) { if (cur == null) return; TreeNode pre_node = pre.get(0); pre_node.left = null; pre_node.right = cur; TreeNode left = cur.left; TreeNode right = cur.right; pre.set(0, cur); helper(left, pre); helper(right, pre); }}
[LeetCode#114]Flatten Binary Tree to Linked List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。