94. Binary Tree Inorder Traversal

Link

難易度 : Easy

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

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

這一題如同另外兩種操作一樣，最一開始就先寫最簡單的recursive的作法

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

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

            InorderTree(current.left,list);
            list.add(current.val);
            InorderTree(current.right,list);
        }
    }

接下來就照慣例完成iteratively的寫法，這邊比較特別是作法與preorder或postorder不太一樣，可以互相比較一下差異

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

接下來最後一種做法就是通用的寫法，基本上只有小地方要異動而已

    //common style
    class Solution3
    {
        public List<Integer> inorderTraversal(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);
                    }
                    stack.push(current);
                    stack.push(null);
                    if(current.left!=null) 
                    {
                        stack.push(current.left);
                    }   

                }
            }           
            return list;
        }       
    }

其實對於preorder、postorder、inorder的作法，我也不知道為啥就是想不出有什麼好寫的，因此這三篇的內容都有點貧脊沒有錯QQ