遞歸的代碼是以前數(shù)據(jù)結(jié)構(gòu)書上常見的：

public ArrayList<Integer> inorderTraversal(ConstructBinaryTreefromPostorderandInorderTraversal.TreeNode root) {ArrayList<Integer> res = new ArrayList<>();dfs(res, root);return res;}private void dfs(List<Integer> res, ConstructBinaryTreefromPostorderandInorderTraversal.TreeNode node) {if (node == null) return;dfs(res, node.left);res.add(node.val);dfs(res, node.right);} 復(fù)制代碼

非遞歸用stack模擬中序遍歷，要理解啊，不能死記硬背。注意while條件和while里面的if。

public class Solution {public ArrayList<Integer> inorderTraversal(TreeNode root) {ArrayList<Integer> res = new ArrayList<>();LinkedList<TreeNode> stack = new LinkedList<>();//注意while條件是或while (root != null || !stack.isEmpty()){if (root!=null){stack.push(root);root = root.left;}else {root = stack.pop();res.add(root.val);root = root.right;}}return res;} } 復(fù)制代碼

---

MAR 25TH 這題今天做98. Validate Binary Search Tree 的時候又來復(fù)習(xí)了一遍，又忘的差不多了。。記得當(dāng)時還在考慮為什么while里面要用||而不是&&。

這題還可以這樣寫：

public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if(root == null) return list;Stack<TreeNode> stack = new Stack<>();while(root != null || !stack.empty()){while(root != null){stack.push(root);root = root.left;}root = stack.pop();list.add(root.val);root = root.right;}return list; } 復(fù)制代碼

---

JULY 29 REVIEW

又看了一遍迭代的方法，仍然寫不出。。上面那個代碼，兩個while循環(huán)其實(shí)挺清晰的，但是root = root.right那邊還是挺難想到的。還有就是外層的while，兩種情況；1是root!= null的情況，這種比較好考慮，就是首次進(jìn)入的時候；2是root==null的情況，statck不為空，這種就是dfs到棧最底的情況。

轉(zhuǎn)載于:https://juejin.im/post/5a3132fef265da432d281a4b

總結(jié)

以上是生活随笔為你收集整理的94 Binary Tree Inorder Traversal的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。