Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/144.html

144	Binary Tree Preorder Traversal

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

For example:
Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

@tag-tree

Algorithm

Use stack to assist calculations. Since the order of pre-order traversal is “root-left-right”, the algorithm is:

1. Push the root node onto the stack
2. Loop to check whether the stack is empty. If it is not empty, take out the top element of the stack, save its value, and then check whether the right child node exists, and push it to the stack if it exists. Look at its left child node, if it exists, push it to the stack.

Code

Java

• Java
• C++
• Python

• import java.util.ArrayList;
  import java.util.List;
  import java.util.Stack;
  
  public class Binary_Tree_Preorder_Traversal {
  
  	/**
  	 * Definition for a binary tree node.
  	 * public class TreeNode {
  	 *     int val;
  	 *     TreeNode left;
  	 *     TreeNode right;
  	 *     TreeNode(int x) { val = x; }
  	 * }
  	 */
  	public class Solution {
  	    public List<Integer> preorderTraversal(TreeNode root) {
  
  	        List<Integer> list = new ArrayList<>();
  
  	        if (root == null) {
  	            return list;
  	        }
  
  	        Stack<TreeNode> sk = new Stack<>();
  	        sk.push(root);
  
  	        while (!sk.isEmpty()) {
  	            TreeNode current = sk.pop();
  
  	            list.add(current.val); // when pushing, ensure non-null got pushed in
  
  	            if (current.right != null) {
  	                sk.push(current.right);
  	            }
  	            if (current.left != null) {
  	                sk.push(current.left);
  	            }
  
  	        }
  
  	        return list;
  
  	    }
  	}
  
  }
  

• // OJ: https://leetcode.com/problems/binary-tree-preorder-traversal/
  // Time: O(N)
  // Space: O(H)
  class Solution {
      vector<int> ans;
      void dfs(TreeNode *root) {
          if (!root) return;
          ans.push_back(root->val);
          dfs(root->left);
          dfs(root->right);
      }
  public:
      vector<int> preorderTraversal(TreeNode* root) {
          dfs(root);
          return ans;
      }
  };
  

• # Definition for a binary tree node.
  # class TreeNode:
  #     def __init__(self, val=0, left=None, right=None):
  #         self.val = val
  #         self.left = left
  #         self.right = right
  class Solution:
      def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
          ans = []
          while root:
              if root.left is None:
                  ans.append(root.val)
                  root = root.right
              else:
                  prev = root.left
                  while prev.right and prev.right != root:
                      prev = prev.right
                  if prev.right is None:
                      ans.append(root.val)
                      prev.right = root
                      root = root.left
                  else:
                      prev.right = None
                      root = root.right
          return ans
  
  ############
  
  # Definition for a binary tree node.
  # class TreeNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution(object):
    def preorderTraversal(self, root):
      res, stack = [], [(1, root)]
      while stack:
        p = stack.pop()
        if not p[1]: continue
        stack.extend([(1, p[1].right), (1, p[1].left), (0, p[1])]) if p[0] != 0 else res.append(p[1].val)
      return res
  
  

All Problems

All Solutions