FilesExpand file tree

 master

/

FlattenBinaryTreeToLinkedList.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

71 lines (63 loc) · 1.71 KB

 master

/

FlattenBinaryTreeToLinkedList.java

Copy path

Top

File metadata and controls

• Code
• Blame

71 lines (63 loc) · 1.71 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

/**

* Practiced on 12/4/2012

*

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

*

* For example,

* Given

*

* 1

* / \

* 2 5

* / \ \

* 3 4 6

* The flattened tree should look like:

* 1

* \

* 2

* \

* 3

* \

* 4

* \

* 5

* \

* 6

*

*==================================

*

* The idea is to process left and right branch first. Then, change the left branch to right

* and connect original right branch to the end of the renewed right branch (which is the original

* left branch).

*

* Here we need to keep tracking the end of left branch, such that we can connect the original

* right branch to the end of the original left branch in O(1) time. Otherwise we need to take

* time to search for the end, which is extra cost.

*/

package com.congli.leetcode;

public class FlattenBinaryTreeToLinkedList {

public void flatten(TreeNode root)

{

helper(root);

}

private TreeNode helper(TreeNode root)

{

if(root == null) return null;

if(root.left == null && root.right == null) return root;

if(root.left == null) return helper(root.right);

if(root.right == null)

{

TreeNode leftEnd = helper(root.left);

root.right = root.left;

root.left = null;

return leftEnd;

}

TreeNode leftEnd = helper(root.left);

TreeNode rightEnd = helper(root.right);

TreeNode temp = root.right;

root.right = root.left;

root.left = null;

leftEnd.right = temp;

return rightEnd;

}

}