二叉树最大深度/宽度 |
您所在的位置：网站首页 › python二叉树深度计算 › 二叉树最大深度/宽度 |
|
题目 https://leetcode-cn.com/problems/maximum-width-of-binary-tree/ https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/ 深度——DFS # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def maxDepth(self, root: TreeNode) -> int: if not root: return 0 return max(self.maxDepth(root.left), self.maxDepth(root.right))+1当前深度为左右子树最大深度+1 宽度——层序遍历 想法宽度即按层来计算，所以采用层序遍历，所注意的一点是：普通层序遍历在对列pop一点，随机可以加入两个子节点，但是在本题中各层应该分开储存，以便于计算每层的节点数（即宽度） 关于宽度，采用二叉树节点在数组中的位置，即某节点为i，则左孩子为i*2，右孩子为i*2+1，父节点为 int(i/2) class Solution: def widthOfBinaryTree(self, root: TreeNode) -> int: if not root: return 0 ans = 1 queue = [(0, root)] # 起始坐标，节点 while queue: ans = max(ans, queue[-1][0] - queue[0][0] + 1) # 每次循环都是一层，计算上一层宽度 temp = [] # 临时数组，实现每层的替换 for i, node in queue: if node.left: # 子树为空，不加入 temp.append((2*i, node.left)) if node.right: temp.append((2*i+1, node.right)) queue = temp return ans
|
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |