编写2、 编写非递归遍历算法，实现：给定一棵二叉树的先序遍历序列和中序遍历序列，创建这文树。 (1)输出二叉树的后序遍历的结点序列。 (2)输出二叉树的叶子结点。 (3)统计二叉树的结点个数。 . (4)求二叉树的深度。

1. 编写非递归遍历算法

对于二叉树的遍历，常用的非递归方法有使用栈和Morris遍历。这里我们使用栈实现非递归遍历。

先序遍历：

def preorder(root):
    stack = [root]
    res = []
    while stack:
        node = stack.pop()
        if node:
            res.append(node.val)
            stack.append(node.right)
            stack.append(node.left)
    return res

中序遍历：

def inorder(root):
    stack = []
    node = root
    res = []
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        res.append(node.val)
        node = node.right
    return res

后序遍历：

def postorder(root):
    stack = [(root, False)]
    res = []
    while stack:
        node, visited = stack.pop()
        if node:
            if visited:
                res.append(node.val)
            else:
                stack.append((node, True))
                stack.append((node.right, False))
                stack.append((node.left, False))
    return res

2. 实现给定一棵二叉树的先序遍历序列和中序遍历序列，创建这棵树。

我们可以使用递归的方式进行构建。先序遍历的第一个节点必定是根节点，然后在中序遍历中找到这个节点，左边的是左子树，右边的是右子树。

代码实现如下：

def buildTree(preorder, inorder):
    if not preorder or not inorder:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    idx = inorder.index(root_val)
    root.left = buildTree(preorder[1:idx+1], inorder[:idx])
    root.right = buildTree(preorder[idx+1:], inorder[idx+1:])
    return root

3. 输出二叉树的后序遍历结点序列

后序遍历的顺序是左右根，可以使用递归的方式实现：

def postorderTraversal(root):
    if not root:
        return []
    return postorderTraversal(root.left) + postorderTraversal(root.right) + [root.val]

也可以使用非递归的方式实现，类似于非递归的先序遍历：

def postorderTraversal(root):
    if not root:
        return []
    stack = [(root, False)]
    res = []
    while stack:
        node, visited = stack.pop()
        if node:
            if visited:
                res.append(node.val)
            else:
                stack.append((node, True))
                stack.append((node.right, False))
                stack.append((node.left, False))
    return res

4. 输出二叉树的叶子结点

叶子结点是指没有左右子树的节点，在遍历的过程中，遇到叶子结点就把它加到结果中即可。可以使用递归的方式实现。

def getLeaves(root):
    if not root:
        return []
    if not root.left and not root.right:
        return [root.val]
    return getLeaves(root.left) + getLeaves(root.right)

也可以使用非递归的方式实现，使用栈来记录遍历的节点：

def getLeaves(root):
    if not root:
        return []
    stack = [root]
    res = []
    while stack:
        node = stack.pop()
        if node:
            if not node.left and not node.right:
                res.append(node.val)
            else:
                stack.append(node.right)
                stack.append(node.left)
    return res

5. 统计二叉树的结点个数

二叉树的结点个数包括根节点、左子树的结点个数和右子树的结点个数。可以使用递归的方式实现。

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

也可以使用非递归的方式实现，使用栈来记录遍历的节点：

def countNodes(root):
    if not root:
        return 0
    stack = [root]
    count = 0
    while stack:
        node = stack.pop()
        if node:
            count += 1
            stack.append(node.left)
            stack.append(node.right)
    return count

6. 求二叉树的深度

二叉树的深度等于左右子树深度的最大值加1。可以使用递归的方式实现。

def maxDepth(root):
    if not root:
        return 0
    return max(maxDepth(root.left), maxDepth(root.right)) + 1

也可以使用非递归的方式实现，使用队列来记录遍历的节点，并记录每个节点的深度：

def maxDepth(root):
    if not root:
        return 0
    queue = [(root, 1)]
    depth = 0
    while queue:
        node, cur_depth = queue.pop(0)
        if node:
            depth = max(depth, cur_depth)
            queue.append((node.left, cur_depth+1))
            queue.append((node.right, cur_depth+1))
    return depth