8000 finish Leetcode MEDIUM Flatten Binary Tree to Lindedin List · jacobklo/jalgorithmCPP@bd4aec3 · GitHub
[go: up one dir, main page]
Skip to content

Commit bd4aec3

Browse files
jacobklojacobklo
committed
finish Leetcode MEDIUM Flatten Binary Tree to Lindedin List
1 parent 88ea946 commit bd4aec3

File tree

3 files changed

+78
-2
lines changed

3 files changed

+78
-2
lines changed

‎README.md

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -81,5 +81,8 @@ unlike normal projects.
8181
* [Util ContainersToString](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/String/ContainersToString.h)
8282
* [Sherlock and the Valid String](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/String/SherlockValidString.h)
8383
* [Unique Emails - LeetCode](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/String/UniqueEmails.h)
84-
8584
***
85+
86+
#### Tree
87+
* [FlattenBinaryTreeToList - LeetCode MEDIUM](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Tree/FlattenBinaryTreeList.h)
88+
***
8000

‎src/CMakeLists.txt

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -55,5 +55,5 @@ add_executable(jalgorithmCPP
5555
Heap/KClosest.h
5656
Dictionary/SubdomainVisitCount.h
5757
String/UniqueEmails.h
58-
)
58+
Tree/FlattenBinaryTreeList.h)
5959

‎src/Tree/FlattenBinaryTreeList.h

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
//
2+
// Created by Jacob Lo on Jan 18, 2019
3+
//
4+
5+
// MEDIUM
6+
// https://leetcode.com/problems/flatten-binary-tree-to-linked-list/
7+
// Given a binary tree, flatten it to a linked list in-place.
8+
//
9+
//For example, given the following tree:
10+
//
11+
// 1
12+
// / \
13+
// 2 5
14+
// / \ \
15+
//3 4 6
16+
//The flattened tree should look like:
17+
//
18+
//1
19+
// \
20+
// 2
21+
// \
22+
// 3
23+
// \
24+
// 4
25+
// \
26+
// 5
27+
// \
28+
// 6
29+
30+
#pragma once
31+
32+
33+
namespace FlattenBinaryTreeList {
34+
struct TreeNode {
35+
int val;
36+
TreeNode *left;
37+
TreeNode *right;
38+
39+
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
40+
};
41+
42+
TreeNode *flattenRec(TreeNode *n) {
43+
44+
if (!n) return nullptr;
45+
46+
TreeNode *listedRight = flattenRec(n->right);
47+
48+
/// if no child, or only right child
49+
if (!n->left) {
50+
n->right = listedRight;
51+
return n;
52+
}
53+
54+
TreeNode *listedLeft = flattenRec(n->left);
55+
56+
TreeNode *lastOfRightNodeInListedLeft = listedLeft;
57+
while (lastOfRightNodeInListedLeft->right != nullptr) {
58+
lastOfRightNodeInListedLeft = lastOfRightNodeInListedLeft->right;
59+
}
60+
61+
n->left = nullptr;
62+
n->right = listedLeft;
63+
lastOfRightNodeInListedLeft->right = listedRight;
64+
65+
return n;
66+
}
67+
68+
void flatten(TreeNode *root) {
69+
70+
flattenRec(root);
71+
}
72+
73+
}

0 commit comments

Comments
 (0)
0