平衡二叉树
平衡二叉树
给你一个二叉树的根节点 root ，判断它是否是平衡二叉树。
平衡二叉树-递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def isBalanced(self, root: Optional[TreeNode]) -> bool:
if self.get_h(root) == -1:
return False
else:
return True
def get_h(self,node):
if not node:
return 0
left_h = self.get_h(node.left)
if left_h == -1:
return -1
elif (right_h := self.get_h(node.right)) == -1:
return -1
elif abs(left_h - right_h)>1:
return -1
else:
return max(left_h,right_h)+1
|
通过后序遍历的方式计算每个节点的高度，并判断其左右子树的高度差是否超过1，若超过则返回-1表示不平衡，否则返回节点的高度。其中可以用海象运算符（:=）来简化代码，避免重复计算。
二叉树的所有路径
二叉树的所有路径
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
二叉树的所有路径-递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution:
def dfs(self,cur,path,result):
path.append(cur.val)
if not cur.left and not cur.right:
result.append("->".join(map(str,path)))
return
if cur.left:
self.dfs(cur.left,path,result)
path.pop()
if cur.right:
self.dfs(cur.right,path,result)
path.pop()
def binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
result = []
if not root:
return result
path = []
self.dfs(root,path,result)
return result
|
因为是从根节点出发查找路径，很容易想到用前序遍历的方式来实现。
在递归中其实是包含了回溯的过程，每次递归结束后，都需要将当前节点从路径中弹出，以确保路径的正确性。
左叶子之和
左叶子之和
给你二叉树的根节点 root ，返回所有左叶子节点的和。
左叶子之和-递归
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution:
def sumOfLeftLeaves(self, root: Optional[TreeNode]) -> int:
if not root :
return 0
if not root.left and not root.right:
return 0
leftnum = self.sumOfLeftLeaves(root.left)
if root.left and not root.left.left and not root.left.right:
leftnum = root.left.val
rightnum = self.sumOfLeftLeaves(root.right)
sum_val = leftnum + rightnum
return sum_val
|
采用后序遍历的方式，先计算左子树的左叶子节点之和，再计算右子树的左叶子节点之和，最后将它们相加即可。
判断当前节点的左子节点是否为左叶子节点（即左子节点没有左右子节点），若为左叶子节点，则将其值加入左子树的左叶子节点之和中。
完全二叉树的节点个数
完全二叉树的节点个数
给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
完全二叉树的节点个数-递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
left = root.left
right= root.right
ld = 0
rd = 0
while left:
left = left.left
ld += 1
while right:
right = right.right
rd += 1
if ld==rd:
return 2**(ld+1)-1
leftnum = self.countNodes(root.left)
rightnum = self.countNodes(root.right)
result = leftnum + rightnum + 1
return result
|
通过计算左子树和右子树的深度，判断当前节点是否为满二叉树的根节点。如果是，则直接计算节点数（2^（ld+1）-1）；否则递归计算左右子树的节点数并相加。这个方法其实是找满二叉树的根节点，满二叉树的节点数为2^（ld+1）-1。从而减少时间复杂度。
也可以用普通后序遍历的方式来实现，但是时间复杂度会高一些。
