這題目出現在這 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;
}
沒感覺嗎 ? 多寫幾次就會有了.
如果要考 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;
}
沒感覺嗎 ? 多寫幾次就會有了.
