DAY 25
0

## 【從面試題學邏輯-25】在不使用遞迴的情況下先序走訪二元樹（leetcode 144. Binary Tree Preorder Traversal）

1. Node有先後順序問題，先序就是「印出當下Node的val→走左邊→走右邊」，也就是下面還有Node的話，要把當下的Node先記起來，左邊走完再回來這個Node找右邊的Node
2. 下一個Node如果又有Node往下，就又必須記Node
3. 最後記的Node要優先走，然後依序往回找Node

``````class Solution {
public List<Integer> preorderTraversal(TreeNode root)
{
TreeNode currentNode = root;
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> result = new ArrayList<Integer>();
while(!stack.isEmpty() || currentNode!=null)
{
if(currentNode!=null) {
stack.push(currentNode);
currentNode = currentNode.left;
} else {
currentNode = stack.pop();
currentNode = currentNode.right;
}
}
return result;
}
}
``````
``````TreeNode currentNode = root;
Stack<TreeNode> stack = new Stack<TreeNode>();
List<Integer> result = new ArrayList<Integer>();
``````

`stack`則是幫我們暫時記住上面提到的，下面還有Node的Node
`result`顧名思義就是放結果

``````while(!stack.isEmpty() || currentNode!=null)
``````

``````if(currentNode!=null){
stack.push(currentNode);
currentNode = currentNode.left;
} else {
currentNode = stack.pop();
currentNode = currentNode.right;
}
``````