设计二叉树的双序遍历算法

二叉树的双序遍历算法，也称为前序遍历和后序遍历算法，是一种常用的二叉树遍历算法。

前序遍历算法：

1. 访问根节点
2. 前序遍历左子树
3. 前序遍历右子树

后序遍历算法：

1. 后序遍历左子树
2. 后序遍历右子树
3. 访问根节点

实现代码如下：

//前序遍历算法
void preOrderTraversal(TreeNode* root) {
if (root) {
cout << root->val << " "; //访问根节点
preOrderTraversal(root->left); //前序遍历左子树
preOrderTraversal(root->right); //前序遍历右子树
}
}

//后序遍历算法
void postOrderTraversal(TreeNode* root) {
if (root) {
postOrderTraversal(root->left); //后序遍历左子树
postOrderTraversal(root->right); //后序遍历右子树
cout << root->val << " "; //访问根节点
}
}

相关问题

以二叉链表作为二叉树的存储结构，编写如下算法：设计二叉树的双序遍历算法

双序遍历也叫做中心序列+扩展先序列遍历，是一种遍历二叉树的方法。下面是采用二叉链表作为二叉树存储结构的双序遍历算法：

1. 初始化：建立一个栈

2. 若根节点不为空，则将当前节点入栈，并将当前节点指向左子树，直到当前节点为空

3. 当前节点为空时，判断栈是否为空

4. 若栈非空，则将栈顶节点出栈，并将当前节点指向右子树

5. 否则，遍历结束

6. 在出栈过程中，进行中序遍历，并在节点入栈操作之前输出节点的值，这是扩展先序遍历

下面是该算法的 Python 代码实现:

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

def double_order_traversal(root: TreeNode) -> None:
    stack = []
    cur = root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        print(cur.val, end=' ')
        cur = cur.right

这个算法的时间复杂度是 O(N)，其中 N 是二叉树中节点的个数。它的空间复杂度是 O(h)，其中 h 是二叉树的高度。

以二叉链表作为二叉树的存储结构，设计以下算法。 (1)统计二叉树的叶结点个数。 (2)判别两棵树是否相等。 (3)交换二叉树每个结点的左孩子和右孩子。 (4)设计二叉树的双序遍历算法(双序遍历是指对于二叉树的每一个结点来说，先访问

该节点的左子树的最右下结点，再访问该节点本身，最后访问该节点的右子树的最左下结点。)

(1) 统计二叉树的叶结点个数算法：

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

(2) 判别两棵树是否相等算法：

def is_same_tree(p, q):
    if not p and not q:
        return True
    elif not p or not q:
        return False
    elif p.val != q.val:
        return False
    else:
        return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

(3) 交换二叉树每个结点的左孩子和右孩子算法：

def swap_left_right(root):
    if not root:
        return
    
    root.left, root.right = root.right, root.left
    
    swap_left_right(root.left)
    swap_left_right(root.right)

(4) 设计二叉树的双序遍历算法：

def double_order_traversal(root):
    if not root:
        return
    
    if root.left:
        node = root.left
        while node.right:
            node = node.right
        print(node.val)
    
    print(root.val)
    
    if root.right:
        node = root.right
        while node.left:
            node = node.left
        print(node.val)
    
    double_order_traversal(root.left)
    double_order_traversal(root.right)

注意：这里的双序遍历是一种特殊的遍历方式，并不是二叉树的常规遍历方式。