Given the root of a binary tree, flatten the tree into a "linked list":
The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
The "linked list" should be in the same order as a pre-order traversal of the binary tree.
Example 1:
- Input: root = [1,2,5,3,4,null,6]
- Output: [1,null,2,null,3,null,4,null,5,null,6]
Example 2:
- Input: root = []
- Output: []
Example 3:
- Input: root = [0]
- Output: [0]
Constraints:
The number of nodes in the tree is in the range [0, 2000].
-100 <= Node.val <= 100
var flatten = function (root) {
let nextOne = null;
const update = (node) => {
if (!node) return node;
update(node.right);
update(node.left);
node.right = nextOne;
node.left = null;
nextOne = node;
};
update(root);
};
전위 순회, 중위 순회, 후위 순회가 있는 것처럼 이번에는 오른쪽, 왼쪽, 중앙 순으로 순회하는 방식으로 순회를 해야했다. 그래서 update의 재귀를 right, left 순으로 실시했다.
binary tree 문제를 보면 아직도 턱턱 막히는 부분이 있는데, 그동안 풀이들을 보면, 시작은 대부분 몇가지 안에서 시작하기 때문에, 그동안 풀이 방식으로부터 실마리를 찾기 시작해야겠다.