二叉树的递归遍历

递归的三要素

1. 确定递归函数的参数和返回值
2. 确定终止条件
3. 确定每一层函数的运行逻辑

二叉树的前序遍历

void PreOrder(TreeNode* root)
{
    if(NULL == root)      //遇到空节点返回
    {
        return; 
    }
    std::cout << root->val <<std::endl;    //先输出根节点的值
    PreOrder(root->left);      //递归左子树
    PreOrder(root->right);        //递归右子树
}

二叉树的中序遍历

void InOrder(TreeNode* root)
{
    if(NULL == root)      //遇到空节点返回
    {
        return; 
    }
    PreOrder(root->left);      //递归左子树
    std::cout << root->val <<std::endl;    //输出根节点的值
    PreOrder(root->right);        //递归右子树
}

二叉树的后序遍历

void PostOrder(TreeNode* root)
{
    if(NULL == root)      //遇到空节点返回
    {
        return; 
    }
    PreOrder(root->left);      //递归左子树
    PreOrder(root->right);        //递归右子树
    std::cout << root->val <<std::endl;    //输出根节点的值
}