FilesExpand file tree

 master

/

100_SameTree100.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

79 lines (74 loc) · 2.04 KB

 master

/

100_SameTree100.java

Copy path

Top

File metadata and controls

• Code
• Blame

79 lines (74 loc) · 2.04 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

/**

* Given two binary trees, write a function to check if they are the same or not.

*

* Two binary trees are considered the same if they are structurally identical

* and the nodes have the same value.

*

* Example 1:

*

* Input: 1 1

* / \ / \

* 2 3 2 3

*

* [1,2,3], [1,2,3]

*

* Output: true

*

* Example 2:

*

* Input: 1 1

* / \

* 2 2

*

* [1,2], [1,null,2]

*

* Output: false

*

* Example 3:

*

* Input: 1 1

* / \ / \

* 2 1 1 2

*

* [1,2,1], [1,1,2]

*

* Output: false

*

*/

/**

* Definition for a binary tree node.

* public class TreeNode {

* int val;

* TreeNode left;

* TreeNode right;

* TreeNode(int x) { val = x; }

* }

*/

public class SameTree100 {

public boolean isSameTree(TreeNode p, TreeNode q) {

if (p == null && q == null) return true;

if (p == null || q == null || p.val != q.val) return false;

return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

}

/**

* https://leetcode.com/problems/same-tree/discuss/32684/My-non-recursive-method

*/

public boolean isSameTree2(TreeNode p, TreeNode q) {

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

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

if (p != null) stack_p.push( p ) ;

if (q != null) stack_q.push( q ) ;

while (!stack_p.isEmpty() && !stack_q.isEmpty()) {

TreeNode pn = stack_p.pop() ;

TreeNode qn = stack_q.pop() ;

if (pn.val != qn.val) return false ;

if (pn.right != null) stack_p.push(pn.right) ;

if (qn.right != null) stack_q.push(qn.right) ;

if (stack_p.size() != stack_q.size()) return false ;

if (pn.left != null) stack_p.push(pn.left) ;

if (qn.left != null) stack_q.push(qn.left) ;

if (stack_p.size() != stack_q.size()) return false ;

}

return stack_p.size() == stack_q.size() ;

}

}