目录
描述
方法一: 递归
Java 代码
方法二: 非递归 (使用栈)
Java 代码
描述
给定一个二叉树, 返回它的前序遍历.
示例:
输入: [1,null,2,3]
- 1
- \
- 2
- /
- 3
输出: [1,2,3]
进阶: 递归算法很简单, 你可以通过迭代算法完成吗?
方法一: 递归
Java 代码
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public List<Integer> preorderTraversal(TreeNode root) {
- List<Integer> res = new ArrayList<>();
- preorderTraversal(root, res);
- return res;
- }
- private void preorderTraversal(TreeNode root, List<Integer> res) {
- if (root == null) {
- return;
- }
- res.add(root.val);
- preorderTraversal(root.left, res);
- preorderTraversal(root.right, res);
- }
- }
复杂度分析:
时间复杂度:\(O(n)\), 其中,\(n\) 为二叉树节点的数目
空间复杂度:\(O(n)\)
方法二: 非递归 (使用栈)
Java 代码
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public List<Integer> preorderTraversal(TreeNode root) {
- List<Integer> res = new ArrayList<>();
- if (root == null) {
- return res;
- }
- Stack<TreeNode> stack = new Stack<>();
- stack.push(root);
- while (!stack.isEmpty()) {
- TreeNode cur = stack.pop();
- res.add(cur.val);
- if (cur.right != null) {
- stack.push(cur.right);
- }
- if (cur.left != null) {
- stack.push(cur.left);
- }
- }
- return res;
- }
- }
复杂度分析:
时间复杂度:\(O(n)\), 其中,\(n\) 为二叉树节点的数目
空间复杂度:\(O(h)\), 其中,\(h\) 为二叉树的高度
来源: https://www.cnblogs.com/xugenpeng/p/9775788.html