设计算法求二叉树所包含的叶结点的数目并求二叉树的深度。

以下是求解二叉树叶结点数目和深度的算法：

# 定义二叉树结点类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# 求解二叉树叶结点数目和深度的函数
def count_leaf_and_depth(root):
    if not root:  # 如果根节点为空，返回0
        return 0, 0
    if not root.left and not root.right:  # 如果根节点为叶结点，返回1和1
        return 1, 1
    left_leaf, left_depth = count_leaf_and_depth(root.left)  # 递归计算左子树的叶结点数目和深度
    right_leaf, right_depth = count_leaf_and_depth(root.right)  # 递归计算右子树的叶结点数目和深度
    leaf = left_leaf + right_leaf  # 计算当前树的叶结点数目
    depth = max(left_depth, right_depth) + 1  # 计算当前树的深度
    return leaf, depth

相关问题

设计算法求二叉树所包含的叶结点的数目并求二叉树的深度。并给出设计思想

以下是求解二叉树叶结点数目和深度的算法及设计思想：

1.算法思想：

- 对于二叉树的叶结点数目，可以通过递归的方式来实现。具体而言，对于每个节点，如果它是叶结点，则将计数器加1；否则，递归遍历它的左右子树，将左右子树的叶结点数目相加即可。
- 对于二叉树的深度，同样可以通过递归的方式来实现。具体而言，对于每个节点，如果它是叶结点，则返回0；否则，递归遍历它的左右子树，将左右子树的深度较大值加1即可。

2.算法实现：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def count_leaves(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    return count_leaves(root.left) + count_leaves(root.right)

def max_depth(root):
    if not root:
        return 0
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    return max(left_depth, right_depth) + 1

3.相关问题：

1．按先序序列构造一棵二叉链表表示的二叉树T； 2．对这棵二叉树进行递归遍历：先序、中序、后序以及层次遍历遍历序列，分别输出结点的遍历序列； 3. 对这棵树用非递归方式进行遍历：先序、中序以及后序遍历序列，分别输出结点的遍历序列； 4．求二叉树的深度/结点数目/叶结点数目； 5．将二叉树每个结点的左右子树交换位置； 6. 设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）； 7. 计算二叉树最大宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）； 8. 求二叉树中第一条最长的路径长度，并输出此路径上各结点。

1. 以先序序列ABD##E##CF###构造的二叉树如下：

       A
     /   \
    B     C
   / \   
  D   E 

2. 递归遍历：

- 先序遍历序列：ABDECF
- 中序遍历序列：DBEAFC
- 后序遍历序列：DEBFCA
- 层次遍历序列：ABCDEF

3. 非递归遍历：

- 先序遍历序列：ABDECF

  先将根节点A入栈，然后循环执行以下操作：
  1. 弹出栈顶节点，输出该节点的值；
  2. 将该节点的右子节点入栈（如果有的话）；
  3. 将该节点的左子节点入栈（如果有的话）。
  循环结束条件为栈为空。

- 中序遍历序列：DBEAFC

  将根节点A入栈，然后循环执行以下操作：
  1. 如果栈顶节点有左子节点，则将其左子节点入栈，并将该节点的左子节点置为null；
  2. 如果栈顶节点没有左子节点，则弹出栈顶节点，输出该节点的值，并将该节点的右子节点入栈（如果有的话）。
  循环结束条件为栈为空。

- 后序遍历序列：DEBFCA

  将根节点A入栈，然后循环执行以下操作：
  1. 如果栈顶节点有左子节点或右子节点，则按左子节点、右子节点、根节点的顺序入栈；
  2. 如果栈顶节点既没有左子节点也没有右子节点，则弹出栈顶节点，输出该节点的值；
  循环结束条件为栈为空。

4. 深度：3，结点数目：6，叶结点数目：3。

5. 交换左右子树后的二叉树如下：

       A
     /   \
    C     B
        /   \   
       E     D

6. 双序遍历序列：ABCEDBF

算法实现：
1. 将根节点入栈，循环执行以下操作：
2. 如果栈不为空，则弹出栈顶节点，输出该节点的值，并将其右子节点入栈（如果有的话）；
3. 如果该节点有左子节点，则将其左子节点入栈，并将该节点的左子节点置为null；
4. 如果该节点没有左子节点，但是右子节点不为空，则将该节点入栈，并将该节点的右子节点置为null。
5. 循环结束条件为栈为空。

7. 最大宽度为3，即第3层的结点数目最多。

8. 最长路径为5，路径为A-B-E-D-C，其中各结点为A、B、E、D、C。