二叉树的前序排列（数据结构C++）

一、问题描述

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

 

二、前序遍历的顺序

前序遍历的顺序 根节点->左子节点->右子节点

（中序遍历的顺序左子节点->根节点->右子节点；后序遍历的顺序左子节点->右子节点->根节点）

三、解题思路

根据前序遍历的顺序是先访问左子树，再访问右子树；利用先进后出，初始化一个栈，先把右子树存储进来，然后里有一个动态数组把遍历后的结果存储起来。

步骤：定义 preorder(root) 表示当前遍历到 root 节点的答案。按照定义，首先将 root 节点的值加入答案，然后递归调用 preorder(root.left) 来遍历 root 节点的左子树，最后递归调用 preorder(root.right) 来遍历 root 节点的右子树即可，递归终止的条件为碰到空节点。

代码如下：

四、运行结果：