144.二叉樹的前序遍歷

題目鏈接
前、中、后的遍歷的遞歸做法實(shí)際上都是一樣的，區(qū)別就是遍歷操作的位置不同。

對于先序遍歷，也就是先根，即把查看當(dāng)前結(jié)點(diǎn)的操作放在最前面即可。

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();preorder(root,res);return res;}public void preorder(TreeNode root, List<Integer> result) {if (root == null) {return;}result.add(root.val);preorder(root.left, result);preorder(root.right, result);}
}

而中序和后序遍歷也是一樣：

// 中序
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();midorder(root,res);return res;}public void midorder(TreeNode root, List<Integer> res){if(root == null){return;}midorder(root.left,res);res.add(root.val);midorder(root.right,res);}
}
//后序
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();postorder(root,res);return res;}public void postorder(TreeNode root, List<Integer> res){if(root == null){return;}postorder(root.left,res);postorder(root.right,res);res.add(root.val);}
}

python版本也一樣，這里就寫一種：

class Solution:def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:res = []def dfs(root):if root is None:return dfs(root.left)dfs(root.right)res.append(root.val)dfs(root)  # 調(diào)用dfs函數(shù)開始遍歷return res

如果不用遞歸，那會(huì)有一點(diǎn)麻煩，但也僅僅是代碼上的。因?yàn)檫f歸本身就是借用系統(tǒng)棧，而使用迭代則是自己創(chuàng)建棧進(jìn)行操作即可。

前序則是將根節(jié)點(diǎn)入棧，后續(xù)的結(jié)點(diǎn)是按照先右邊再左邊的順序入棧（因?yàn)槲覀円忍幚碜笞?#xff0c;因此左子后入?？梢韵缺籶op）。

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null){return res;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode tmp = stack.pop();res.add(tmp.val);if(tmp.right != null){stack.push(tmp.right);}if(tmp.left != null){stack.push(tmp.left);}}return res;}
}

但中后序的操作和前序不太一樣（雖然有方法可以進(jìn)行統(tǒng)一，但本文不贅述）。而后序則是將先序（根左右）進(jìn)行操作（根左右->根右左->左右根），即調(diào)整處理順序+反轉(zhuǎn)數(shù)組。

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

102 二叉樹的層序遍歷

題目鏈接
層序遍歷用的是隊(duì)列，每次將一個(gè)節(jié)點(diǎn)入隊(duì)，處理完當(dāng)前節(jié)點(diǎn)，則其子節(jié)點(diǎn)分別入隊(duì)，下一輪再處理子節(jié)點(diǎn)，也就是下一層的內(nèi)容。

例如，一棵樹為1、2、3、4、5（數(shù)組表示），那么第一次是1入隊(duì)，處理完1后，1的子節(jié)點(diǎn)也就是2、3入隊(duì)。處理完2，也就是2的子節(jié)點(diǎn)入隊(duì)，即4、5。3處理后沒有子節(jié)點(diǎn)，就剩下4、5需要處理。

如果是要求返回的是一個(gè)列表，沒有嵌套結(jié)構(gòu)，那就會(huì)好做很多，我們就按照上面的流程構(gòu)造隊(duì)列然后不斷處理即可。但現(xiàn)在返回的要求是每一層都要有一個(gè)單獨(dú)的列表，因此就麻煩一些。

我們就使用兩重循環(huán)，第一重是記錄隊(duì)列是否為空，第二重則是看當(dāng)前遍歷的層。

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<TreeNode> deque = new LinkedList<>();List<List<Integer>> res = new ArrayList<List<Integer>>();if(root == null){return res;}deque.add(root);while(!deque.isEmpty()){// len記錄當(dāng)前層的個(gè)數(shù)，tmpList則是存放當(dāng)前層，最后統(tǒng)一add到res上int len = deque.size();List<Integer> tmpList = new ArrayList<>();while(len>0){TreeNode tmpNode = deque.removeFirst();tmpList.add(tmpNode.val);if(tmpNode.left!=null){deque.add(tmpNode.left);}if(tmpNode.right!=null){deque.add(tmpNode.right);}len--;}res.add(tmpList);}return res;}
}