LeetCode每日一题,144. Binary Tree Preorder Traversal
先看题目描述
大意就是给定一个二叉树,让我们返回其先序遍历序列
算法和思路
递归
直接用递归的算法十分简单,定义 dfs(root, res) 表示当前遍历到 root 节点的答案,那么按照定义,我们只要递归调用 dfs(root.left, res) 来遍历root 节点的左子树,然后将 root 节点的值加入答案,再递归调用 dfs(root.right, res) 来遍历 root 节点的右子树即可,递归终止的条件为碰到空节点
栈
其实就是上一方法中的递归函数用迭代来实现,两种方式等价。区别在于递归的时候维护了一个隐形的栈,而在迭代的时候则是显式的将这个栈模拟出来
算法源码
递归
1 | import java.util.*; |
栈
1 | class Solution { |