#35 Coding面試 - LeetCode #94 Binary Tree Inorder Traversal

這題目出現在這 https://leetcode.com/problems/binary-tree-inorder-traversal/

如果要考 Tree 相關的題目,這一題算是相當經典的考試題目了.我想經典的原因就是 Tree inorder traversal 是資料結構課本裡面一定會教到的內容.大部份的課本裡面都會提供 recursive 的方式來做 inorder traversal,其程式如下

        public List<int> InorderTraversal(TreeNode root)
        {
            List<int> result = new List<int> ();
            if (root == null) return result;
            if (root.left != null)
                result.AddRange(InorderTraversal(root.left));
            result.Add(root.val);
            if (root.right != null)
                result.AddRange(InorderTraversal(root.right));
            return result;
        }

但面試官既然要考你這一題的話,絕對不可能只問你 recursive 如何寫,也一定還會問你怎麼用 iterative 的方式來寫.
如果你完全沒做過相關的練習,一時之間還真的很難想的出來該怎麼把 recursive 改成 iterative. 在這可以分享一件小事,因為寫 recursive 有階層的關係,所以程式的 call stack 就一層一層往上加,上一層結束回到下一層時也自然知道該從什麼地方繼續執行.但是若改用 iterative 的話,就沒有這種記住上次執行到那的好處了.對於這種需要記住位置的情況,就可以直接想想 Stack,因為 Stack 能幫助我們記住走過的痕跡.

所以,改成 iterative 的程式碼如下

        public List<int> InorderTraversal(TreeNode root)
        {
            List<int> result = new List<int> ();
            if (root == null) return result;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode node = root;
            while (stack.Count != 0 || node != null)
            {
                if (node != null)
                {
                    stack.Push(node);     // <-- 幫我們記住位置
                    node = node.left;
                }
                else
                {
                    TreeNode temp = stack.Pop();    // <-- 把上次記住的位置拿出來
                    result.Add(temp.val);
                    node = temp.right;
                }                              
            }
            return result;
        }

沒感覺嗎 ? 多寫幾次就會有了.

Share:

0 意見:

張貼留言