題目:Given a binary tree, return the inorder traversal of its nodes’ values.
解題思路:樹的非遞歸周遊,先序,中序,後序都用棧,層序用隊列。建議最好寫非遞歸的
代碼:
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public List<Integer> inorderTraversal(TreeNode root) {
//非遞歸中序周遊
Stack<TreeNode> stack = new Stack<>();
ArrayList<Integer> ans = new ArrayList<>();
if(root == null) return ans;
while (root !=null ||!stack.isEmpty()) {
while (root != null) {
stack.push(root);
root = root.left;
}
if (!stack.isEmpty()) {
root = stack.pop();
ans.add(root.val);
root = root.right;
}
}
return ans;
}