二叉树相关算法问题解析与实现
平衡二叉树判断
给定一个二叉树，判断它是否为平衡二叉树。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：true
示例 2：
输入：root = [1,2,2,3,3,null,null,4,4]
输出：false
递归解法：
# 定义节点类
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def checkBalance(self, root):
return self.checkHeight(root) != -1
def checkHeight(self, node):
if not node:
return 0
leftHeight = self.checkHeight(node.left)
rightHeight = self.checkHeight(node.right)
if leftHeight == -1 or rightHeight == -1 or abs(leftHeight - rightHeight) > 1:
return -1
return max(leftHeight, rightHeight) + 1
获取所有根到叶子的路径
返回从根节点到所有叶子节点的路径。
示例：
输入：root = [1,2,3,null,5]
输出：["1->2->5", "1->3"]
迭代解法：
class Solution:
def findPaths(self, root):
if not root:
return []
stack, pathStack, result = [root], [str(root.val)], []
while stack:
current = stack.pop()
path = pathStack.pop()
if not current.left and not current.right:
result.append(path)
if current.right:
stack.append(current.right)
pathStack.append(f"{path}->{current.right.val}")
if current.left:
stack.append(current.left)
pathStack.append(f"{path}->{current.left.val}")
return result
计算左叶子节点之和
给定一棵二叉树，返回所有左叶子节点的值的总和。
示例：
输入：root = [3,9,20,null,null,15,7]
输出：24
递归解法：
class Solution:
def sumLeftLeaves(self, root):
totalSum = 0
def helper(node, isLeft):
nonlocal totalSum
if not node:
return
if not node.left and not node.right and isLeft:
totalSum += node.val
helper(node.left, True)
helper(node.right, False)
helper(root, False)
return totalSum
完全二叉树节点计数
计算一棵完全二叉树的节点总数。
示例：
输入：root = [1,2,3,4,5,6]
输出：6
优化解法：
class Solution:
def countNodes(self, root):
if not root:
return 0
leftDepth = rightDepth = 0
leftNode, rightNode = root, root
while leftNode:
leftDepth += 1
leftNode = leftNode.left
while rightNode:
rightDepth += 1
rightNode = rightNode.right
if leftDepth == rightDepth:
return (1 << leftDepth) - 1
return 1 + self.countNodes(root.left) + self.countNodes(root.right)
