目錄

LeetCode-94題

---

LeetCode-94題

給定一個二叉樹的根節點root，返回它的中序遍歷結果。?

class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();order(root, result);return result;}private void order(TreeNode root, List<Integer> mid) {//當前節點TreeNode curr = root;//借助棧LinkedList<TreeNode> stack = new LinkedList<>();//最近一次pop的元素TreeNode pop = null;while (curr != null || !stack.isEmpty()) {if (curr != null) {stack.push(curr);//待處理左節點curr = curr.left;} else {//棧不為空TreeNode peek = stack.peek();//右節點為空if (peek.right == null) {mid.add(peek.val);pop = stack.pop();}//右節點處理完else if (peek.right == pop) {pop = stack.pop();}//處理右節點else {mid.add(peek.val);curr = peek.right;}}}}
}