FilesExpand file tree

 master

/

BinaryTreeInorderTraverse.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

89 lines (81 loc) · 2.26 KB

 master

/

BinaryTreeInorderTraverse.java

Copy path

Top

File metadata and controls

• Code
• Blame

89 lines (81 loc) · 2.26 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

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

/**

* Practiced on 11/28/2012

*

* Inorder traverse a tree using iterative method.

*

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

* The first function is written by myself, which is way more complicated than the second one.

*

*/

package com.congli.leetcode;

import java.util.ArrayList;

import java.util.HashSet;

import java.util.Stack;

public class BinaryTreeInorderTraverse {

public ArrayList<Integer> inorderTraversal(TreeNode root)

{

ArrayList<Integer> result = new ArrayList<Integer>();

Stack<TreeNode> list = new Stack<TreeNode>();

HashSet<TreeNode> set = new HashSet<TreeNode>();

if(root == null) return result;

list.add(root);

while(!list.isEmpty())

{

TreeNode node = list.peek();

if(node.left == null && node.right == null)

{

result.add(node.val);

list.pop();

}

else if(node.left != null && !set.contains(node.left))

{

list.add(node.left);

set.add(node.left);

}

else

{

if(node.right != null && !set.contains(node.right))

{

result.add(node.val);

list.add(node.right);

set.add(node.right);

}

else

{

list.pop();

if(node.right == null)

{

result.add(node.val);

}

}

}

}

return result;

}

public static void inOrderIterate(TreeNode node)

{

Stack<TreeNode> stack = new Stack<TreeNode>();

boolean stop = false;

while(!stop)

{

if(node != null)

{

stack.push(node);

node = node.left;

}

else

{

if(stack.isEmpty())

{

stop = true;

}

else

{

node = stack.pop();

System.out.print(node.val + " ");

node = node.right;

}

}

}

}

}