二叉树

/* 递归版前序遍历 */
void Tree::preOrderWithRecursive(ListNode* root) {
    if (root == nullptr)return;
    std::cout << root->val << " ";
    preOrderNoRecursive(root->left);
    preOrderNoRecursive(root->right);
}

/* 非递归版前序遍历 */
void Tree::preOrderNoRecursive(ListNode* root) {
    if (root == nullptr)return;
    std::stack<ListNode*> s;
    ListNode* p = root;
    // 在下边的循环中，可以将p看做树的根节点以及子树的根节点
    while (!s.empty() || p)
    {
        while (p)
        {
            std::cout << p->val << " ";
            s.push(p);
            p = p->left;
        }
        if (!s.empty())
        {
            p = s.top();
            s.pop();
            // std::cout << p->val << " ";
            p = p->right; // 将p指向其右子树
        }
    }
}

/* 递归版中序遍历 */
void Tree::inOrderWithRecursive(ListNode* root) {
    if (root == nullptr)return;
    inOrderNoRecursive(root->left);
    std::cout << root->val << " ";
    inOrderNoRecursive(root->right);
}


/* 非递归版中序遍历 */
// 和前序遍历的代码几乎一样，只是取值的位置换了
void Tree::inOrderNoRecursive(ListNode* root) {
    if (root == nullptr)return;
    std::stack<ListNode*> s;
    ListNode* p = root;
    // 在下边的循环中，可以将p看做树的根节点以及子树的根节点
    while (!s.empty() || p)
    {
        while (p)
        {
            s.push(p);
            p = p->left;
        }
        if (!s.empty()) 
        {
            p = s.top();
            s.pop();
            std::cout << p->val << " ";
            p = p->right; // 将p指向其右子树
        }
    }
}

/* 递归版后序遍历 */
void Tree::postOrderWithRecursive(ListNode* root) {
    if (root == nullptr)return;
    postOrderNoRecursive(root->left);
    postOrderNoRecursive(root->right);
    std::cout << root->val << " ";
}
/* 非递归版后序遍历 */
// 后序遍历稍微复杂一点，因为需要判断上次遍历的是节点的左子树还是右子树
void Tree::postOrderNoRecursive(ListNode* root) {
    if (root == nullptr) return;
    std::stack<ListNode*> s;
    ListNode* p = root;
    ListNode* last = nullptr; // 这里多了一个变量，用来指向上次输出的节点，作用是判断上次输出的是左子树还是右子树

    while (p)
    {
        s.push(p);
        p = p->left;
    }

    while (!s.empty() || p)
    {
        p = s.top();
        s.pop();
        if (p->right == nullptr || p->right == last) // p的右子树为空，或者上次输出了p的右子树
        {
            std::cout << p->val << " ";
            last = p;
        }
        else
        {
            s.push(p);
            p = p->right;
            while (p)
            {
                s.push(p);
                p = p->left;
            }
        }
    }
}