python實作二叉樹的堂兄弟節點
一采用遞回法
利用哈希映射代碼如下
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
if not root:
return False
parent={} #樹的父節點
depth={} #樹的深度
def tree(root,par=None):
if root:
if par:
depth[root.val]=1+depth[par]
else:
depth[root.val]=1
parent[root.val]=par
tree(root.left,root.val)
tree(root.right,root.val)
tree(root)
return depth[x]==depth[y] and parent[x]!=parent[y]
二采用迭代的方法
采用的是層次遍歷的思想 ，如果兩個節點在同一層并且父節點不一樣的話回傳True 否則回傳False
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def isCousins(self, root: TreeNode, x: int, y: int) -> bool:
if not root:
return False
迭代
ls=[root]
while ls:
li=[]
ac=[]
for _ in range(len(ls)):
b=[]
a=ls.pop()
if a.right:
li.append(a.right)
ac.append(a.right.val)
b.append(a.right.val)
if a.left:
li.append(a.left)
ac.append(a.left.val)
b.append(a.left.val)
if b:
if x in b and y in b:
return False
if x in ac and y in ac and (x not in b or y not in b):
return True
ls=li
return False
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/189666.html
標籤：其他
上一篇：發送帶附件的郵件