Solution by <monkeykingyan>


  • 0

    Approach #1 Recursive [Accepted]

    Detail Explanation
    The first method to solve this problem is using recursive.
    This is the classical method and straightforward. we can define a helper function to implement recursion.
    The java code is as following:

    Java

    public List<Integer> preorderTraversal(TreeNode root) {
      List<Integer> res = new ArrayList<>();
      helper(root, res);
      return res;
    }
    
    public void helper(TreeNode root, List<Integer> res) {
      if (root != null) {
        res.add(root.val);
        if (root.left != null) {
          helper(root.left, res);
        }
        if (root.right != null) {
          helper(root.right, res);
        }
      }
    }
    
    
    

    Complexity Analysis

    • Time complexity : $$O(n)$$. The time complexity is $$O(n)$$ because the recursive function is $$T(n) = 2*T(n/2)+1$$.

    • Space complexity : The worst case is $$O(n)$$, and the average case is $$O(log(n))$$ where $$ n $$ is number of nodes.
      a lot of people will have the question, why the worst case is $$O(n)$$?
      it is because the space complexity is related to the height of the tree when the tree is balanced, the height is $$O(log(n))$$, the worst case is $$O(n)$$.


    Approach #2 Iterating method using Stack [Accepted]

    Detail Explanation
    The strategy is very similar to the first method, the different is using a stack. For each node
    if the node is not null, we add it's value in the result, then if the node has the right child,
    push the right in the stack and if the node has left child, update node as it's left child.
    if the stack is not empty and the node is null, we update the node as stack.pop().

    Here is an Example:
    
           1
         /   \
        2     3
       / \
      4   5
      
    initial: res[]; curr = 1; stack[];
    step1 : res[1]; curr = 2; stack[3];
    step2 : res[1,2]; curr = 4; stack[3,5];
    step3 : res[1,2,4]; curr = null; stack[3,5];
    step4 : curr == null && stack is not empty -> curr = 5; stack[3];
    step5 : res[1,2,4,5]; curr == null; stack[3];
    step6 : curr == null && stack is not empty -> curr = 3; stack[];
    step7 : res[1,2,4,5,3]; curr == null; stack is empty;
    step8 : return [1,2,4,5,3]
    
    Comment: the preorder traversal is root->root.left->root.right,
    if the root.right is not null, we push it in the stack,
    which make sure the order we process the right subtree,
    this is the reason we use stack.
    
    
    

    Java

    class Solution {
    	public List<Integer> preorderTraversal(TreeNode root) {
    		List<Integer> res = new ArrayList<>();
    		Stack<TreeNode> stack = new Stack<>();
    		TreeNode curr = root;
    		while (curr != null) {
    			res.add(curr.val);
    
    			if (curr.right != null) {
    				stack.push(curr.right);
    			}
    			curr = curr.left;
    			if (curr == null && !stack.isEmpty()) {
    				curr = stack.pop();
    			}
    		}
    		return res;
    	}
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$.

    • Space complexity : $$O(n)$$.


    Approach #3 Morris Traversal [Accepted]

    Detail Explanation

    This method we have to use a new data structure Threaded Binary Tree and the strategy is as follows:

    Step1. Initialize current as root
    Step2. While current is not NULL
     If current does not have left child
     a. Add current’s value
     b. Go to the right, i.e., current = current.right
    Else
     a. add current's value.
     b. In current's left subtree, make current's right the right child of the rightmost node in left subtree.
     c. Go to this left child, i.e., current = current.left
    
    For Example:
      curr->(1)
           /   \
          2     3
         / \   /
        4   5 6
    res[];
    First: 1 is the root, so initial 1 as current, 1 has left child which is 2, the current's left subtree is
            2
           / \
          4   5
    so in this subtree, the rightmost node is 5, then make the current(1)'s right as the right child of 5. Set current = cuurent.left (current = 2).
    The tree now looks like:
              1
             /
    curr-> (2)
           / \
          4   5
               \
                3
                /
              6
    res[1];
    For current, 2, which has left child 4, so make the current's right as it's left subtree's right most node(4)'s right child
               1
              /
             2
            /
    curr->(4)
            \
              5
               \
                3
                /
               6
    res[1,2];
    then add 4 because it has no left child, then add 5,3 one by one, for node 3 which has left child 6, do the same as above.
    Finally, the inoder taversal is [1,2,4,5,3,6].
    

    For more detail, please check

    Threaded binary tree

    Java

    class Solution {
    public List<Integer> preorderTraversal(TreeNode node) {
    	    List<Integer> list = new ArrayList();
    	    while(node != null) {
    	        if(node.left == null) {
    	            list.add(node.val);
    	            node = node.right;
    	        }
    	        else {
    	            TreeNode nextNode = node.left;
    
    	            TreeNode p = nextNode;
    	            while(p.right != null) p = p.right;
    
    	            list.add(node.val);
    	            p.right = node.right;
    	            node = nextNode;
    	        }
    	    }
    	    return list;
    	}
    
    }
    

    Complexity Analysis

    • Time complexity : $$O(n)$$. To prove that the time complexity is $$O(n)$$,
      the biggest problem lies in finding the time complexity of finding the predecessor nodes of all the nodes in the binary tree.
      Intuitively, that complexity is $$O(nlogn)$$, because to find the predecessor node for a single node related to the height of the tree.
      But in fact, finding the predecessor nodes for all nodes only needs $$O(n)$$ time. Because n nodes in a Binary-Tree has n-1 edges, the whole processing for each edges up to 2 times, one is to locate a node, and the other is to find the predecessor node.
      So the complexity is $$O(n)$$.
    • Space complexity : $$O(1)$$. The space complexity of Morris Traversal is $$O(1)$$ because it just needs 2 "assisting" pointers. (TreeNode p and TreeNode nextNode)

    Related Links

    Video Explanation

    Samiliar Questions

    LeetCode 94: Binary Tree Inorder Traversall

    Solution 94


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.