Binary Tree Preorder Traversal

 

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

 

Given:

1   / \  2   3 / \4   5

return [1,2,4,5,3].

Challenge

Can you do it without recursion?

 

前序遍历两种方式，递归与非递归方式。

首先要明确前序遍历，顺序是先父节点，然后左子节点，右子节点。

 

The key to solve this problem is to understand the following:

1. What is preorder? (parent node is processed before its children）

使用递归的方法：

/** * Definition of TreeNode: * public class TreeNode { *     public int val; *     public TreeNode left, right; *     public TreeNode(int val) { *         this.val = val; *         this.left = this.right = null; *     } * } */public class Solution {    /**     * @param root: The root of binary tree.     * @return: Preorder in ArrayList which contains node values.     */    ArrayList
        
          list=new ArrayList
         
          ();    public ArrayList
          
            preorderTraversal(TreeNode root) {        // write your code here        if(root!=null)        {            helper(root);        }        return list;    }        public void helper(TreeNode p)    {        list.add(p.val);        if(p.left!=null)        {            helper(p.left);        }                if(p.right!=null)        {            helper(p.right);        }            }}
          
         
        

 

非递归：

1. Use Stack from Java Core library
2. It is not obvious what preorder for some strange cases. However, if you draw a stack and manually execute the program, how each element is pushed and popped is obvious.

The key to solve this problem is using a stack to store left and right children, and push right child first so that it is processed after the left child.

 

public class TreeNode {    int val;    TreeNode left;    TreeNode right;    TreeNode(int x) { val = x; }} public class Solution {    public ArrayList
        
          preorderTraversal(TreeNode root) {        ArrayList
         
           list = new ArrayList
          
           ();         if(root == null)            return list;         Stack
           
             stack = new Stack
            
             ();        stack.push(root);         while(!stack.empty()){            TreeNode cur= stack.pop();            list.add(cur.val);             if(cur.right != null){                stack.push(cur.right);            }            if(n.left != null){                stack.push(cur.left);            }         }        return list;    }}
            
           
          
         
        

Keep in mind that stack is a FILO data type, so when we process the data, we need to push the right children first, and then left children.