104.二叉树的最大深度
递归后序
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def getDepth(root):
if not root:
return 0
depth = 0
leftdepth = getDepth(root.left)# 左
rightdepth = getDepth(root.right)# 右
depth = max(leftdepth, rightdepth) + 1# 中 算上本层的结点 所以加1
return depth
if not root:
return 0
d =getDepth(root)
return d
迭代法
# 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 maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
que = deque([root])
k = 0 # 记录遍历的层数
while que:
r = []
size = len(que)
for i in range(size):
cur = que.popleft()
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
k+=1
return k
559.n叉树的最大深度
"""
# Definition for a Node.
class Node:
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution:
def maxDepth(self, root: 'Node') -> int:
def getDepth(root):
if not root:
return 0
depth = 0
# 参考后序左右中 所以n叉树 孩子遍历也是左右中 同时每次与上一次的
for child in root.children:
depth = max(depth,getDepth(child))
depth += 1 # 中
return depth
if not root:
return 0
d = getDepth(root)
return d
迭代法
"""
# Definition for a Node.
class Node(object):
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
class Solution(object):
def maxDepth(self, root):
"""
:type root: Node
:rtype: int
"""
if not root:
return 0
que = deque([root])
d = 0
while que:
size = len(que)
d+=1
for _ in range(size):
cur = que.popleft()
if cur.children:# 孩子不空
que.extend(cur.children)
return d
111.二叉树的最小深度
递归
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def getDepth(root):
if not root:
return 0
leftdepth = getDepth(root.left)
rightdepth = getDepth(root.right)
#左孩空 右不为空，这时并不是最低点
if not root.left and root.right:
return rightdepth + 1
# 右孩空 左不为空，这时并不是最低点
elif root.left and not root.right:
return leftdepth + 1
depth = 1 + min(leftdepth,rightdepth)
return depth
if not root:
return 0
return getDepth(root)
迭代
# 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 minDepth(self, root: TreeNode) -> int:
if not root:
return 0
k = 1 # 根节点深度1
que = deque([(root,1)])
while que:
size = len(que)
for i in range(size):
cur,k = que.popleft()
# 假设是根节点 左右孩子都空 则返回k
if cur.left == None and cur.right == None:
return k
# 因为在一个for循环内 有左还右孩子 层数都加1
if cur.left:
que.append((cur.left,k+1))
if cur.right:
que.append((cur.right,k+1))
return 0
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
que = deque()
que.append(root)
res = 1
while que:
for _ in range(len(que)):
node = que.popleft()
# 当左右孩子都为空的时候，说明是最低点的一层了，退出
if not node.left and not node.right:
return res
if node.left is not None:
que.append(node.left)
if node.right is not None:
que.append(node.right)
res += 1
return res
222. 完全二叉树的节点个数
迭代法
# 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 countNodes(self, root: TreeNode) -> int:
if not root:
return 0
num = 0
que = deque([root])
while que:
size = len(que)
for _ in range (size):
num += 1
cur = que.popleft()
if cur.left:
que.append(cur.left)
if cur.right:
que.append(cur.right)
return num
递归法
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def getNode(root):
if not root:
return 0
leftnum = getNode(root.left) # 左
rightnum = getNode(root.right) # 右
num = leftnum + rightnum + 1 #中
return num
return getNode(root)
110.平衡二叉树
二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。（往下数在第几层）
二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数（往上数在第几层）
因为求深度可以从上到下去查 所以需要前序遍历（中左右），而高度只能从下到上去查，所以只能后序遍历（左右中）
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def isBalanced(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
if self.getHeight(root) != -1:
return True
else:
return False
def getHeight(self, root):
if not root: # 为空 高度0
return 0
lh = self.getHeight(root.left)# 左
if lh == -1:
return -1
rh = self.getHeight(root.right)# 右
if rh == -1:
return -1
if abs(lh - rh) > 1:#中
return -1
# 以当前节点为根节点的树的最大高度 因为需要算上当前结点的高度
else:
return 1 + max(lh, rh)
257. 二叉树的所有路径
注：回溯和递归是一一对应的，有一个递归，就要有一个回溯
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def binaryTreePaths(self, root):
"""
:type root: TreeNode
:rtype: List[str]
"""
if not root:
return[]
res = []
self.getPath(root,'', res)
return res
def getPath(self, root, path, res):
if not root:
return
path += str(root.val) #中
# 处理单层逻辑 如果到叶子节点 加入列表中
if not root.left and not root.right:
res.append(path)
else:
path += '->'
self.getPath(root.left, path, res)#左
self.getPath(root.right, path, res)#右
404. 左叶子之和
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def sumOfLeftLeaves(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# 边界
if not root:
return 0
cur_val = 0
left_sum = self.sumOfLeftLeaves(root.left)# 左
right_sum = self.sumOfLeftLeaves(root.right)# 右
# 中 处理单层逻辑 判断是不是左叶子 首先是左然后是叶子
if root.left != None and root.left.left == None and root.left.right == None:
cur_val = root.left.val
return cur_val + left_sum + right_sum
513.找树左下角的值
思路：层序遍历 在树的最后一行找到最左边的值。
