【面试】判断一棵树是否是平衡二叉树

总结

• 此题是华为AI实习生一面笔试题。
• python可以同时返回多个变量，即一个tuple。
• 博客来源：LawsonAbs@CSDN

---

题意

判断一棵二叉树是否是平衡二叉树。

代码

写代码的时候，需要严格按照逻辑来，不能有一丁点儿的纰漏

class TreeNode():
def __init__(self,left,right) -> None:
self.left = left
self.right = right


class Solution():
# 返回节点的高度
def dfs(self,node):
if node is None:
return (0,1) # 0 代表的是高度，1代表是否该节点的根的数是否是二叉树

left = self.dfs(node.left)
right = self.dfs(node.right)

if abs(left[0] - right[0]) < 2 and left[1] and right[1] : # 如果高度差小于2
return (max(left[0],right[0])+1,1)
else:
return (max(left[0],right[0])+1,0)


node4 = TreeNode(None,None)
node3 = TreeNode(None,None)
node2 = TreeNode(node4,None)
node1 = TreeNode(node2,node3)

s = Solution()
out = s.dfs(node1)
print(out)