leetcode-114-Flatten-Binary-Tree-to-Linked-List

发表于   |  

描述

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

For example, given the following tree:

1
2
3
4
5
    1
   / \
  2   5
 / \   \
3   4   6

The flattened tree should look like:

1
2
3
4
5
6
7
8
9
10
11
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

分析

利用栈来解决这个问题，当遇到右子树时先入栈，如果左子树不为空，将其作为右子树，如果左子树为空，出栈，将其作为右子树，不断迭代右子树，直到栈为空。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode p = root;
        
        while(p != null || !stack.empty()) {
            if (p.right != null) {
                stack.push(p.right);
            }
            if (p.left != null) {
                p.right = p.left;
                p.left = null;
            } else if (!stack.empty()) {
                TreeNode tmp = stack.pop();
                p.right = tmp;
            }
            p = p.right;
        }
    }
}

相关问题

题目来源