二叉树后续遍历C++代码

void postorderTraversal(struct TreeNode* root){
if(root == NULL){
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}

相关问题

请给出二叉树后续遍历非递归算法的c++完整代码

当然，以下是二叉树后续遍历的非递归算法的C++完整代码：

#include <stack>
#include <vector>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        if (!root) {
            return res;
        }

        stack<TreeNode*> s;
        TreeNode* last_visited = NULL;
        while (root || !s.empty()) {
            while (root) {
                s.push(root);
                root = root->left;
            }

            root = s.top();
            if (!root->right || root->right == last_visited) {
                res.push_back(root->val);
                s.pop();
                last_visited = root;
                root = NULL; // 这里需要将 root 置空，否则会重复 push 进栈中
            } else {
                root = root->right;
            }
        }
        return res;
    }
};

这里使用了一个栈来模拟递归的过程。首先将根节点入栈，然后将根节点的左子树全部入栈，直到左子树为空。此时，从栈中弹出栈顶元素，如果其右子树为空或已经被访问过，则访问该节点，并将其标记为已访问过，否则将其右子树入栈。重复以上步骤直到栈为空。

C++二叉树的中序遍历

二叉树的中序遍历可以通过递归实现。具体实现过程如下：

1.如果树为空，则返回。

2.对根节点的左子树进行递归遍历。

3.输出根节点的值。

4.对根节点的右子树进行递归遍历。

代码实现如下：

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void inorderTraversal(TreeNode* root) {
    if (root == NULL) return;
    inorderTraversal(root->left);
    cout << root->val << " ";
    inorderTraversal(root->right);
}

在实际使用中，我们可以将中序遍历的结果存储在一个数组中，然后进行后续的操作。