|
| 1 | +/* |
| 2 | + Author: Andy, nkuwjg@gmail.com |
| 3 | + Date: Jan 28, 2015 |
| 4 | + Problem: Flatten Binary Tree to Linked List |
| 5 | + Difficulty: Medium |
| 6 | + Source: https://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/ |
| 7 | + Notes: |
| 8 | + Given a binary tree, flatten it to a linked list in-place. |
| 9 | + For example, |
| 10 | + Given |
| 11 | + 1 |
| 12 | + / \ |
| 13 | + 2 5 |
| 14 | + / \ \ |
| 15 | + 3 4 6 |
| 16 | + The flattened tree should look like: |
| 17 | + 1 |
| 18 | + \ |
| 19 | + 2 |
| 20 | + \ |
| 21 | + 3 |
| 22 | + \ |
| 23 | + 4 |
| 24 | + \ |
| 25 | + 5 |
| 26 | + \ |
| 27 | + 6 |
| 28 | + Hints: |
| 29 | + If you notice carefully in the flattened tree, each node's right child points to the next node |
| 30 | + of a pre-order traversal. |
| 31 | +
|
| 32 | + Solution: Recursion. Return the last element of the flattened sub-tree. |
| 33 | + */ |
| 34 | + |
| 35 | +/** |
| 36 | + * Definition for binary tree |
| 37 | + * public class TreeNode { |
| 38 | + * int val; |
| 39 | + * TreeNode left; |
| 40 | + * TreeNode right; |
| 41 | + * TreeNode(int x) { val = x; } |
| 42 | + * } |
| 43 | + */ |
| 44 | +public class Solution { |
| 45 | + public void flatten(TreeNode root) { |
| 46 | + flatten_3(root); |
| 47 | + } |
| 48 | + public void flatten_1(TreeNode root) { |
| 49 | + if (root == null) return; |
| 50 | + flatten_1(root.left); |
| 51 | + flatten_1(root.right); |
| 52 | + if (root.left == null) return; |
| 53 | + TreeNode node = root.left; |
| 54 | + while (node.right != null) node = node.right; |
| 55 | + node.right = root.right; |
| 56 | + root.right = root.left; |
| 57 | + root.left = null; |
| 58 | + } |
| 59 | + public void flatten_2(TreeNode root) { |
| 60 | + if (root == null) return; |
| 61 | + Stack<TreeNode> stk = new Stack<TreeNode>(); |
| 62 | + stk.push(root); |
| 63 | + while (stk.empty() == false) { |
| 64 | + TreeNode cur = stk.pop(); |
| 65 | + if (cur.right != null) stk.push(cur.right); |
| 66 | + if (cur.left != null) stk.push(cur.left); |
| 67 | + cur.left = null; |
| 68 | + cur.right = stk.empty() == true ? null : stk.peek(); |
| 69 | + } |
| 70 | + } |
| 71 | + public TreeNode flattenRe3(TreeNode root, TreeNode tail) { |
| 72 | + if (root == null) return tail; |
| 73 | + root.right = flattenRe3(root.left, flattenRe3(root.right, tail)); |
| 74 | + root.left = null; |
| 75 | + return root; |
| 76 | + } |
| 77 | + public void flatten_3(TreeNode root) { |
| 78 | + if (root == null) return; |
| 79 | + flattenRe3(root, null); |
| 80 | + } |
| 81 | +} |
| 82 | + |
0 commit comments