思路1:递归。
思路2:非递归。使用栈模拟递归。
class Solution { public List<Integer> preorderTraversal(TreeNode root) { /** *方法1:递归 * 时间复杂度O(n) * 空间复杂度O(n)为递归中栈的开销,平均情况为 O(logn),最坏情况下树呈现链状,为 O(n) */ /* List<Integer> res = new ArrayList<>(); if (root == null) return res; preOrder(root, res); return res; */ /** * 方法2:非递归,使用栈模拟递归 * 时间复杂度O(n) * 空间复杂度O(n)为迭代过程中显式栈的开销 */ List<Integer> ans = new ArrayList<>(); if (root == null) return ans; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode cur = stack.pop(); ans.add(cur.val); if (cur.right != null) // 先压入右子树 stack.push(cur.right); if (cur.left != null) stack.push(cur.left); } return ans; } private void preOrder(TreeNode root, List<Integer> res) { if (root == null) { return; } res.add(root.val); preOrder(root.left, res); preOrder(root.right, res); } }
参考:
原文:https://www.cnblogs.com/HuangYJ/p/14156838.html