二叉樹(shù)

知識(shí)點(diǎn)

二叉樹(shù)遍歷

• 前序遍歷：根節(jié)點(diǎn)->左子樹(shù)->右子樹(shù)
• 中序遍歷：左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)
• 后續(xù)遍歷：左子樹(shù)->右子樹(shù)->根節(jié)點(diǎn)

注意點(diǎn)：

• 以根節(jié)點(diǎn)的訪問(wèn)順序，決定是什么遍歷
• 左子樹(shù)都是優(yōu)先右子樹(shù)

前序遞歸

void preorderHelper(TreeNode* node) {
    if (node == nullptr) return;
    result.push_back(node->val);
    preorderHelper(node->left);
    preorderHelper(node->right);
}

前序非遞歸

// 通過(guò)非遞歸遍歷
template<class TreeNode>
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;  // 保存結(jié)果
    stack<TreeNode*> call;  //調(diào)用棧，最后出棧就是前面的部分結(jié)果
    if (root != nullptr) {
        call.push(root);
    }
    while (!call.empty())
    {
        TreeNode* t = call.top();
        call.pop();   // 返回的是void
        if (t!=nullptr)
        {
            if (t->right) call.push(t->right);  // 右節(jié)點(diǎn)壓棧，最后處理
            if (t->left) call.push(t->left);
            call.push(t); 
            call.push(nullptr);
        }
        else
        {
            res.push_back(call.top()->val); //top()是nullptr之前壓棧的一個(gè)節(jié)點(diǎn)，也就是上面call.push(t)中的那個(gè)t
            call.pop();
        }
    }
    return res;
}