大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定二叉树的根节点，返回节点值的前序遍历。”
2、题目描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1： 输入： root = [1,null,2,3] 输出： [1,2,3]
示例 2： 输入： root = [1] 输出： [1]
二、解题
1、思路分析
二叉树的前序遍历已经说过很多遍了。
也就是从根节点出发，按照左子树→右子树的顺序遍历整个树。
在访问的时候也是左子树→右子树的顺序访问。
按照这种方式遍历整个树，整个遍历的方式就具有递归的性质。
2、代码实现
代码参考：
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); preorder(root, res); return res; } public void preorder(TreeNode root, List<Integer> res) { if (root == null) { return; } res.add(root.val); preorder(root.left, res); preorder(root.right, res); } }
3、时间复杂度
时间复杂度：O(n)
其中n是二叉树的节点数，每个节点整个被遍历一次。
空间复杂度：O(n)
其中n是二叉树的节点数，主要是递归在栈上的开销。
三、总结
首先将根节点的值存入答案
然后递归调用函数，将左子树传递进去，最后递归调用函数，将右子树传递进去。
以前序遍历的方式遍历整棵树，递归终止条件是碰到空节点。
