二叉树

知识点

二叉树遍历

• 前序遍历：根节点->左子树->右子树
• 中序遍历：左子树->根节点->右子树
• 后续遍历：左子树->右子树->根节点

注意点：

• 以根节点的访问顺序，决定是什么遍历
• 左子树都是优先右子树

前序递归

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

前序非递归

// 通过非递归遍历
template<class TreeNode>
vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;  // 保存结果
    stack<TreeNode*> call;  //调用栈，最后出栈就是前面的部分结果
    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);  // 右节点压栈，最后处理
            if (t->left) call.push(t->left);
            call.push(t); 
            call.push(nullptr);
        }
        else
        {
            res.push_back(call.top()->val); //top()是nullptr之前压栈的一个节点，也就是上面call.push(t)中的那个t
            call.pop();
        }
    }
    return res;
}