用递归 非递归两种方法遍历二叉树的设计思想

遍历二叉树是二叉树的基本操作之一，可以使用递归和非递归两种方法实现。

1. 递归遍历二叉树的设计思想：

递归遍历二叉树的基本思想是：将问题转化为规模更小的同类问题的解决，直到问题规模足够小，可以直接求解。对于二叉树的遍历，可以将其分解为遍历根节点、遍历左子树和遍历右子树三个子问题，然后使用递归的方式分别解决这三个子问题，最终得到整棵二叉树的遍历结果。

递归遍历二叉树的代码框架如下：

void traverse(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    // 遍历根节点
    traverse(root->val);
    // 遍历左子树
    traverse(root->left);
    // 遍历右子树
    traverse(root->right);
}

2. 非递归遍历二叉树的设计思想：

非递归遍历二叉树的基本思想是：使用辅助数据结构（如栈）来存储还未遍历的节点，根据遍历顺序依次将节点压入栈中（或弹出栈中的节点），直到所有节点都被遍历完毕。

对于二叉树的遍历，可以使用栈来存储还未遍历的节点，具体操作如下：

- 前序遍历：将根节点压入栈中，然后弹出栈顶节点，并依次将其右子节点和左子节点压入栈中，直到栈为空。
- 中序遍历：将根节点压入栈中，然后沿着左子树一直向下遍历，将遇到的每个节点都压入栈中。当遍历到叶子节点时，弹出栈顶节点并输出，然后转向右子树，重复上述操作，直到栈为空。
- 后序遍历：将根节点压入栈中，然后依次将其左子节点和右子节点压入栈中。当栈顶元素没有左右子节点或者左右子节点都已经被访问过时，弹出栈顶元素并输出。重复上述操作，直到栈为空。

非递归遍历二叉树的代码框架如下：

void traverse(TreeNode* root) {
    stack<TreeNode*> s;
    TreeNode* p = root;
    while (p != NULL || !s.empty()) {
        if (p != NULL) {
            // 遍历当前节点
            s.push(p);
            p = p->left;
        } else {
            p = s.top();
            s.pop();
            // 遍历当前节点
            p = p->right;
        }
    }
}