第六章 树和二叉树作业

1. 请问如何判断一个二叉树是完全二叉树？

答：完全二叉树是指除了最后一层外，其他每一层都是满的，并且最后一层的节点从左到右连续地填满，缺失的节点只能在最后一层的最右侧。因此，判断一个二叉树是否为完全二叉树的方法如下：

- 如果二叉树为空，则它是完全二叉树；
- 如果二叉树不为空，则按照层次遍历的顺序，从上到下、从左到右遍历每个节点，并进行以下判断：

- 如果当前节点有右子树，但没有左子树，则它不是完全二叉树；
- 如果当前节点不是满的（即左子树或右子树为空），那么它之后的所有节点都必须是叶子节点，否则它不是完全二叉树；
- 如果按照层次遍历的顺序遍历完所有节点都满足上述条件，则它是完全二叉树。

2. 请问如何求一棵二叉树的深度？

答：二叉树的深度是指从根节点到最深叶子节点的路径长度。求一棵二叉树的深度可以使用递归的方法：

- 如果二叉树为空，则深度为0；
- 如果二叉树不为空，则深度为1加上左右子树中的最大深度。具体而言，可以先递归求解左子树的深度和右子树的深度，然后取它们的最大值并加1即可。

下面是求解二叉树深度的 Python 代码示例：

def depth(root):
    if root is None:
        return 0
    else:
        left_depth = depth(root.left)
        right_depth = depth(root.right)
        return max(left_depth, right_depth) + 1

3. 请问如何对一棵二叉树进行前序遍历？

答：前序遍历是指先访问根节点，然后按照先左后右的顺序递归遍历左右子树。对于一棵二叉树，可以使用递归或者非递归的方法进行前序遍历。

- 递归方法：如果二叉树为空，则直接返回；否则，先访问根节点，然后递归遍历左子树和右子树。

def preorder_recursive(root):
    if root is None:
        return
    print(root.val)
    preorder_recursive(root.left)
    preorder_recursive(root.right)

- 非递归方法：使用栈来模拟递归的过程。首先将根节点压入栈中，然后每次从栈中弹出一个节点，访问它，并将它的右子节点和左子节点依次压入栈中。

def preorder_iterative(root):
    if root is None:
        return
    stack = [root]
    while stack:
        node = stack.pop()
        print(node.val)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

4. 请问如何对一棵二叉树进行中序遍历？

答：中序遍历是指按照先左后根再右的顺序递归遍历左子树、访问根节点、递归遍历右子树。对于一棵二叉树，可以使用递归或者非递归的方法进行中序遍历。

- 递归方法：如果二叉树为空，则直接返回；否则，先递归遍历左子树，然后访问根节点，最后递归遍历右子树。

def inorder_recursive(root):
    if root is None:
        return
    inorder_recursive(root.left)
    print(root.val)
    inorder_recursive(root.right)

- 非递归方法：使用栈来模拟递归的过程。首先将根节点入栈，并将它的所有左子节点依次入栈，直到没有左子节点。然后每次从栈中弹出一个节点，访问它，并将它的右子节点入栈，并将右子节点的所有左子节点依次入栈。

def inorder_iterative(root):
    if root is None:
        return
    stack = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        print(node.val)
        node = node.right

5. 请问如何对一棵二叉树进行后序遍历？

答：后序遍历是指按照先左后右再根的顺序递归遍历左右子树、访问根节点。对于一棵二叉树，可以使用递归或者非递归的方法进行后序遍历。

- 递归方法：如果二叉树为空，则直接返回；否则，先递归遍历左子树和右子树，最后访问根节点。

def postorder_recursive(root):
    if root is None:
        return
    postorder_recursive(root.left)
    postorder_recursive(root.right)
    print(root.val)

- 非递归方法：使用栈来模拟递归的过程。首先将根节点入栈，然后每次从栈中弹出一个节点，将它的左子节点和右子节点依次入栈。在处理完所有子节点之后，访问弹出的节点。

def postorder_iterative(root):
    if root is None:
        return
    stack1 = [root]
    stack2 = []
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    while stack2:
        node = stack2.pop()
        print(node.val)

注意，在非递归方法中，需要使用两个栈来实现后序遍历。第一个栈用于存储遍历的节点，第二个栈用于存储最终的遍历结果。首先将根节点入第一个栈，然后每次从第一个栈中弹出一个节点，并将它入第二个栈，同时将它的左子节点和右子节点依次入第一个栈。在第一个栈为空时，第二个栈中存储的节点顺序就是后序遍历的结果。