LeetCode 101 對稱二叉樹

2022-09-22 06:41:46 字數 2869 閱讀 8980

問題描述:

給定一個二叉樹,檢查它是否是映象對稱的。

例如,二叉樹[1,2,2,3,4,4,3]是對稱的。

1

/ \2 2

/ \ / \

3 4 4 3

但是下面這個[1,2,2,null,3,null,3]則不是映象對稱的:

1

/ \2 2

\ \

3 3

方法1:用兩個列表模擬棧,初始a棧和b棧分別儲存根節點的左節點和右節點,此後,a的左孩子進棧a,b的右孩子進棧b,a的右孩子進棧a,b的左孩子進棧b。出棧時進行比較,如果不相等則返回false

1

class

solution(object):

2def

issymmetric(self, root):

3"""

4:type root: treenode

5:rtype: bool

6"""7if

notroot:

8return

true

9 stacka, stackb =[root.left], [root.right]

10while stacka and

stackb:

11 a =stacka.pop()

12 b =stackb.pop()

13if

not a and

notb:

14continue

1516

elif

not a or

notb:

17return

false

18elif a.val !=b.val:

19return

false

20else:21

2223

2425

if stacka or

stackb:

26return

false

27else:28

return true

方法2:

1

class

solution(object):

2def

issymmetric(self, root):

3"""

4:type root: treenode

5:rtype: bool

6"""

7if root==none:

8return

true

9if root.left and

root.right:

10if root.left.val!=root.right.val:

11return

false

1213 l_list=

14 r_list=

15def

previsit(self,root):

16if root==none:

1718

return

19if root.left==none and root.right==none:

2021

return

22previsit(self,root.left)

2324

previsit(self,root.right)

2526

defpostvisit(self,root):

27if root==none:

2829

return

30if root.left==none and root.right==none:

3132

return

3334

postvisit(self,root.right)

3536

postvisit(self,root.left)

3738

previsit(self,root.left)

39postvisit(self,root.right)40#

print(l_list)41#

print(r_list)

42return l_list==r_list

l_list=[5,3,6,2,6,4,8]

r_list=[5,3,6,2,6,4,8]

方法3:

1

class

solution(object):

2def

issymmetric(self, root):

3"""

4:type root: treenode

5:rtype: bool

6"""

7def

helper(root,mirror):8if

not root and

notmirror:

9return

true

10if root and mirror and root.val ==mirror.val:

11return helper(root.left,mirror.right) and

helper(root.right,mirror.left)

12return

false

13return helper(root,root)

2018-09-07 19:51:41

LeetCode 101 對稱二叉樹

給定一個二叉樹,檢查它是否是映象對稱的。 例如,二叉樹 1 2 2 3 4 4 3 是對稱的。 1 2 2 3 4 4 3但是下面這個 1...

LeetCode 二叉樹

樹是一種經常用到的資料結構,用來模擬具有樹狀結構性質的資料集合。樹的每一個節點有一個值和一個包含所有子節點的列表,二叉樹是一種更為典型的樹狀結構,每個節點最多有兩個子樹的樹結構,稱作左子樹和右子樹。 前序遍歷首先訪問根節點,然後遍歷左子樹,最後遍歷右子樹。 f b g a d i c e h f b...

LeetCode 平衡二叉樹 110

給定一個二叉樹,判斷它是否是高度平衡的二叉樹。 本題中,一棵高度平衡二叉樹定義為 一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過1...