非递归遍历二叉树的源代码

非递归遍历二叉树的常见做法是使用栈来模拟递归过程。实现过程中，我们需要先将根节点压入栈中，然后循环执行以下操作：

1. 取出栈顶元素，并将其访问（输出或处理）；
2. 将栈顶元素的右子树（如果有）压入栈中；
3. 将栈顶元素的左子树（如果有）压入栈中。

具体代码如下：

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

def inorderTraversal(root: TreeNode) -> List[int]:
    if not root:
        return []

    stack = []
    res = []
    curr = root

    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left

        curr = stack.pop()
        res.append(curr.val)
        curr = curr.right

    return res

以上是中序遍历的代码，前序遍历和后序遍历也可以使用类似的方式实现。只需要在访问节点的时候改变顺序即可。

相关问题

递归遍历二叉树 c++ 代码

递归遍历二叉树的C代码如下所示：

// 定义二叉树节点的数据结构
typedef struct TreeNode{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 递归遍历二叉树的函数
void recursiveTraversal(TreeNode* node){
    // 递归终止条件：节点为空
    if(node == NULL){
        return;
    }

    // 先序遍历：先访问根节点，再递归遍历左右子树
    printf("%d ", node->val);
    recursiveTraversal(node->left);
    recursiveTraversal(node->right);

    // 中序遍历：先递归遍历左子树，再访问根节点，最后递归遍历右子树
    recursiveTraversal(node->left);
    printf("%d ", node->val);
    recursiveTraversal(node->right);

    // 后序遍历：先递归遍历左右子树，再访问根节点
    recursiveTraversal(node->left);
    recursiveTraversal(node->right);
    printf("%d ", node->val);
}

以上代码定义了二叉树节点的数据结构`TreeNode`，其中包含节点的值、左子节点和右子节点。`recursiveTraversal`函数是递归遍历二叉树的主函数，传入根节点作为参数。

在函数内部，首先判断节点是否为空，如果为空则直接返回。然后按照先序遍历、中序遍历和后序遍历的顺序，依次对根节点、左子树和右子树进行递归遍历。在先序遍历中，先访问根节点，再递归遍历左右子树。在中序遍历中，先递归遍历左子树，然后访问根节点，最后递归遍历右子树。在后序遍历中，先递归遍历左右子树，再访问根节点。

在每个遍历过程中，可以根据实际需求对节点进行操作，例如将节点的值打印出来。

以上就是递归遍历二叉树的C代码，通过递归的方式可以方便地遍历整个二叉树。

非递归遍历二叉树c++

非递归遍历二叉树是指在不使用递归函数的情况下，对二叉树进行遍历的方法。以下是三种非递归遍历二叉树的方法：

1. 非递归中序遍历二叉树

中序遍历二叉树的顺序是：左子树 -> 根节点 -> 右子树。使用栈来保存未被访问的节点，具体步骤如下：
1）从根节点开始，将当前节点入栈。
2）如果当前节点有左子树，则将左子树入栈并进入左子树，重复步骤2，直到左子树为空。
3）从栈中弹出节点，访问该节点。
4）如果该节点有右子树，则将右子树入栈并进入右子树，重复步骤2、3、4。

2. 非递归先序遍历二叉树

先序遍历二叉树的顺序是：根节点 -> 左子树 -> 右子树。使用栈来保存未被访问的节点，具体步骤如下：
1）从根节点开始，将当前节点入栈。
2）从栈中弹出节点，访问该节点。
3）如果该节点有右子树，则将右子树入栈。
4）如果该节点有左子树，则将左子树入栈。
5）重复步骤2、3、4，直到栈为空。

3. 非递归后序遍历二叉树

后序遍历二叉树的顺序是：左子树 -> 右子树 -> 根节点。使用两个栈来实现，具体步骤如下：
1）将根节点入栈1。
2）从栈1中弹出节点，并将该节点入栈2。
3）如果该节点有左子树，则将左子树入栈1。
4）如果该节点有右子树，则将右子树入栈1。
5）重复步骤2、3、4，直到栈1为空。
6）从栈2中依次弹出节点并访问。