非递归深度优先遍历代码

非递归深度优先遍历（Non-recursive depth-first traversal）可以借助栈（stack）来实现，以下是基于栈实现的非递归深度优先遍历代码：

def dfs_non_recursive(root):
    if not root:
        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)

解析：

1. 首先判断根节点是否为空，若为空则返回。
2. 创建一个栈，并将根节点放入栈中。
3. 当栈不为空时，弹出栈顶元素（即当前节点），并输出当前节点的值。
4. 如果当前节点有右子节点，则将右子节点入栈。
5. 如果当前节点有左子节点，则将左子节点入栈。
6. 重复步骤 3-5，直到栈为空。

需要注意的是，此处的代码是针对二叉树的深度优先遍历，对于其他类型的图或树，需要根据实际情况进行修改。

相关问题

c++非递归深度优先遍历代码

下面是C++实现非递归深度优先遍历的代码：

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

// 定义节点结构体
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<int> dfs(TreeNode* root) {
    vector<int> res;
    if (!root) {
        return res;
    }

    stack<TreeNode*> s;
    s.push(root);

    while (!s.empty()) {
        TreeNode* cur = s.top();
        s.pop();
        res.push_back(cur->val);

        if (cur->right) {
            s.push(cur->right);
        }

        if (cur->left) {
            s.push(cur->left);
        }
    }

    return res;
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    vector<int> res = dfs(root);
    for (auto val : res) {
        cout << val << " ";
    }

    return 0;
}

这里我们使用了一个栈来保存节点，从而实现了非递归的深度优先遍历。具体的实现细节可以参考代码中的注释。

非递归深度优先遍历树

以下是非递归深度优先遍历树的实现代码：

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

def preorderNonrecursion(root):
    if not root:
        return
    
    stack = []
    stack.append(root)
    
    while stack:
        node = stack.pop()
        visit(node)
        
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

def visit(node):
    print(node.val)

# 创建一个示例树
#      1
#     / \
#    2   3
#   / \
#  4   5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

preorderNonrecursion(root)

输出结果为：

1
2
4
5
3