114. Flatten Binary Tree to Linked List

发表于 | 分类于 | |

114. Flatten Binary Tree to Linked List

题目描述

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
For example,
Given
         1
        / \
       2   5
      / \   \
     3   4   6
The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

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.

题目大意

变二叉树为链表

解题思路

按照右-左-根的顺序遍历二叉树

代码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func flatten(_ root: TreeNode?) {
        var pre: TreeNode?
        func dfs(_ tree: TreeNode?) {
            guard let t = tree else { return }
            dfs(tree?.right)
            dfs(tree?.left)
            
            t.right = pre
            t.left = nil
            pre = t
        }
        dfs(root)
    }
}
0%