2020-10-23python實現二元樹的堂兄弟節點

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