前序遍历、中序遍历、后序遍历
前序遍历： 根节点 左子树的前序遍历结果 右子树的前序遍历结果
中序遍历： 左子树的中序遍历结果 根节点 右子树的中序遍历结果
后序遍历： 左子树的后序遍历结果 右子树的后序遍历结果 根节点
这三种遍历方式主要用来做序列化（如保存到数组中）方便数据的传递。序列化后可以通过：
中序遍历 + 前序遍历
中序遍历 + 后序遍历
来还原二叉树结构，无法通过
前序遍历 + 后序遍历
来还原树结构，没有中序遍历是无法获取左右子树的数量！
前序遍历 (根 左 右)
//前序遍历 (根 左 右 )
void PreOrderTree(TreeNode* root, vector<int> &vecProOrder)
{
if (root == NULL)
{
return;
}
//先输出当前根节点
printf("%d ", root->val);
vecProOrder.push_back(root->val);
//左节点
PreOrderTree(root->left, vecProOrder);
//右节点
PreOrderTree(root->right, vecProOrder);
}
中序遍历 (左 根 右)
//中序遍历 (左 根 右 )
void InOrderTree(TreeNode* root, vector<int>& vecInOrder)
{
if (root == NULL)
{
return;
}
//左节点
InOrderTree(root->left, vecInOrder);
//先输出当前根节点
printf("%d ", root->val);
vecInOrder.push_back(root->val);
//右节点
InOrderTree(root->right, vecInOrder);
}
后序遍历 (左 右 根)
//后序遍历 (左 右 根)
void PostOrderTree(TreeNode* root, vector<int>& vecPostOrder)
{
if (root == NULL)
{
return;
}
//左节点
PostOrderTree(root->left, vecPostOrder);
//右节点
PostOrderTree(root->right, vecPostOrder);
//先输出当前根节点
printf("%d ", root->val);
vecPostOrder.push_back(root->val);
}
