114. Flatten Binary Tree to Linked List

题目：

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

The flattened tree should look like:

click to show hints.

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

链接： http://leetcode.com/problems/flatten-binary-tree-to-linked-list/

5/8/2017

算法班

不要被难倒了，每个节点的left设为null就可以了。熟悉前序遍历

 1 public class Solution {
 2     public void flatten(TreeNode root) {
 3         if (root == null) return;
 4         Stack<TreeNode> stack = new Stack<TreeNode>();
 5         TreeNode prev = null;
 6         TreeNode cur;
 7         stack.push(root);
 8         while (!stack.empty()) {
 9             cur = stack.pop();
10             if (cur.right != null) {
11                 stack.push(cur.right);
12             }
13             if (cur.left != null) {
14                 stack.push(cur.left);
15             }
16             cur.left = null;
17             if (prev != null) {
18                 prev.right = cur;
19             }
20             prev = cur;
21         }
22         return;
23     }
24 }

别人的答案

https://discuss.leetcode.com/topic/5783/accepted-simple-java-solution-iterative

第11，12行很好的方法，避免了prev

 1    public void flatten(TreeNode root) {
 2         if (root == null) return;
 3         Stack<TreeNode> stk = new Stack<TreeNode>();
 4         stk.push(root);
 5         while (!stk.isEmpty()){
 6             TreeNode curr = stk.pop();
 7             if (curr.right!=null)  
 8                  stk.push(curr.right);
 9             if (curr.left!=null)  
10                  stk.push(curr.left);
11             if (!stk.isEmpty()) 
12                  curr.right = stk.peek();
13             curr.left = null;  // dont forget this!! 
14         }
15     }

另外递归的方法

https://discuss.leetcode.com/topic/11444/my-short-post-order-traversal-java-solution-for-share

 1 private TreeNode prev = null;
 2 
 3 public void flatten(TreeNode root) {
 4     if (root == null)
 5         return;
 6     flatten(root.right);
 7     flatten(root.left);
 8     root.right = prev;
 9     root.left = null;
10     prev = root;
11 }