Skip to content

Latest commit

 

History

History
89 lines (82 loc) · 2.21 KB

144. Binary Tree Preorder Traversal.md

File metadata and controls

89 lines (82 loc) · 2.21 KB
Raw

144. Binary Tree Preorder Traversal

leetcode-cn Daily Challenge on October 27th, 2020.

Difficulty : Medium

Related Topics : Stack、Tree

Given the root of a binary tree, return the preorder traversal of its nodes' values.

Example:

1

Input: root = [1,null,2,3]
Output: [1,2,3]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Example 4:

2

Input: root = [1,2]
Output: [1,2]

Example 5:

3

Input: root = [1,null,2]
Output: [1,2]

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • -100 <= Node.val <= 100

Solution

  • mine
    • Java
      • Iterate & LinkedList Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.5 MB, less than 5.17% of Java online submissions 
        public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    LinkedList<TreeNode> stack = new LinkedList<>();
    TreeNode cur = root;
    while(cur != null || !stack.isEmpty()){
        if(cur != null){
            res.add(cur.val);
            stack.push(cur.right);
            cur = cur.left;
        }else{
            cur = stack.pop();
        }
    }
    return res;
}
      • Recursive & LinkedList Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.5 MB, less than 5.17% of Java online submissions 
        public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> res = new LinkedList<>();
    if(root == null){
        return res;
    }
    res.add(root.val);
    res.addAll(preorderTraversal(root.left));
    res.addAll(preorderTraversal(root.right));
    return res;
}