/**

* 144. Binary Tree Preorder Traversal

* https://leetcode.com/problems/binary-tree-preorder-traversal/description/

* @param {TreeNode} root

* @return {number[]}

* Preorder: 根-左-右

*/

var preorderTraversal = function (root) {

　　let stack = [], result = [];

　　while (stack.length > 0 || root != null) {

　　　　while (root != null) {

　　　　　　stack.push(root);

　　　　　　result.push(root.val);//save root first

　　　　　　root = root.left;//push left node

　　　　}

　　　　root = stack.pop();

　　　　root = root.right;

　　}

　　return result;

};

 

//java

public List
      
        preorderTraversal(TreeNode root) {       Stack
       
         stack = new Stack
        
         ();        List
         
           list = new ArrayList
          
           ();        while (root!=null || !stack.empty()){            while (root!=null){                stack.push(root);                list.add(root.val);                root = root.left;            }             root = stack.pop();            root = root.right;        }        return list;    }