題目:
給定一個二叉樹,傳回它的中序 周遊。
示例:
輸入: [1,null,2,3]
1
\
2
/
3
輸出: [1,3,2]
進階: 遞歸算法很簡單,你可以通過疊代算法完成嗎?
代碼實作:
中序周遊的通用實作可以檢視部落格:二叉樹周遊系列--中序周遊
遞歸版本:
class Solution {
private List<Integer> inorder = new ArrayList<Integer>();
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) return inorder;
inorderTraversal(root.left);
inorder.add(root.val);
inorderTraversal(root.right);
return inorder;
}
}
非遞歸版本:
class Solution {
private List<Integer> inorder = new ArrayList<Integer>();
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) return inorder;
TreeNode p = root;
Stack<TreeNode> stack = new Stack<TreeNode>();
while (p != null) {
stack.push(p);
p = p.left;
while(p == null && !stack.isEmpty()) {
p = stack.pop();
inorder.add(p.val);
p = p.right;
}
}
return inorder;
}
}