144. Binary Tree Preorder Traversal

Link

難易度 : Easy

題目是二元樹基本的三種遍尋的操作，這邊附上各篇連結

1. preorder 144
2. inorder 94
3. postorder 145

並且三題都會依照我寫題和別的大神所提供的寫法來一次介紹

1. recursive

2. iteratively

3. common style

========================================

1. recursive

我一開始想到同時應該也是比較容易的做法是recursive的做法，這個作法應該沒什麼好特別介紹的，就是一遍遍的向下找去

    //recursive
    class Solution
    {
        public List<Integer> preorderTraversal(TreeNode root)
        {
            List<Integer> list = new ArrayList<Integer>();
            PreorderTree(root,list);
            return list;
        }

        private void PreorderTree(TreeNode currentNode,List<Integer> list) 
        {
            if(currentNode==null) 
            {
                return;
            }

            list.add(currentNode.val);
            PreorderTree(currentNode.left,list);
            PreorderTree(currentNode.right,list);
        }
    }

2. iteratively

接著題目的follow up要求使用迭代的作法來達成，那從這邊開始就讓我很頭疼，到底要怎麼樣遍尋的過程保存路徑並且依照情況將值存入list呢?

其實使用stack就可以實現recursive的做法，每一層的變數整包存在stack，接著每次pop回來就可以向前推回

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

            return list;
        }       
    }

3. common style

因為同時寫了preorder、postorder、inorder的iteratively作法後發現寫出來的結果風格不統一，因此網上大老也提供了一種思路

在遍尋的過程中加入null的node用來判斷接下來的需要將val存入list中。

實際的思路我這邊就直接提供原文網址

    //common style
    class Solution
    {
        public List<Integer> preorderTraversal(TreeNode root)
        {
            List<Integer> list = new ArrayList<Integer>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            if(root==null) 
            {
                return list;
            }
            stack.push(root);
            while(!stack.isEmpty()) 
            {
                TreeNode current = stack.pop();
                if(current==null) 
                {
                    current = stack.pop();
                    list.add(current.val);
                }
                else 
                {
                    if(current.right!=null) 
                    {
                        stack.push(current.right);
                    }
                    if(current.left!=null) 
                    {
                        stack.push(current.left);
                    }
                    stack.push(current);
                    stack.push(null);
                }
            }

            return list;
        }       
    }

其實整體感想在思考統一風格的iteratively時是比較困難的，至於想到stack來實現recursvie這部分倒是還好