144_二叉樹的前序遍歷
目錄
144_二叉樹的前序遍歷
描述
給定一個二叉樹,返回它的前序 遍歷。
示例:
輸入: [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\) 為二叉樹的高度