二叉樹
這是一個(gè)例子：
二叉樹樹的遍歷方式有兩種屈张，深度優(yōu)先遍歷（Depth First Search）和廣度優(yōu)先遍歷（Bread First Search）村视。深度的話就是一條路能走就先走到頭僚祷，然后再走另外一條路章姓，關(guān)于左右走哪條路的順序不同袭灯，分為先根质欲，中根，后根三種祠丝；而廣度顧名思義就是一層一層的往下遍歷疾呻，在這一層徹底找完了再往下一層遍歷除嘹。
中序遍歷
思路
即遍歷順序?yàn)橹懈颍蟾野段希缟蠄D例子的順序即為：2,5,6,11,7,2,5,4,9
遞歸算法很容易想到尉咕，先遞歸調(diào)用左子樹，再輸出自身值璃岳，再遞歸調(diào)用右子樹年缎。
一切遞歸算法都能轉(zhuǎn)化成非遞歸算法。中序遍歷的非遞歸算法稍微復(fù)雜一點(diǎn)矾睦，但大概思路就是把遞歸的函數(shù)棧轉(zhuǎn)化實(shí)際編程語言中的對(duì)象棧晦款。
申請(qǐng)一個(gè)棧，從根節(jié)點(diǎn)出發(fā)把左子樹全部入棧枚冗，然后在出棧一個(gè)節(jié)點(diǎn)的時(shí)候缓溅，把它的右子樹的左節(jié)點(diǎn)也全部入棧，其實(shí)這個(gè)和遞歸的思路是一模一樣的赁温。
遞歸代碼
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
helper(root, res);
return res;
}
private void helper(TreeNode root, List<Integer> res) {
if (root == null) return;
helper(root.left, res);
res.add(root.val);
helper(root.right, res);
}
}
非遞歸代碼
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
TreeNode ptr = root;
Stack<TreeNode> stack = new Stack();
while (ptr != null) { // 入棧所有左子樹
stack.push(ptr);
ptr = ptr.left;
}
List<Integer> result = new LinkedList<>();
while (stack.size() != 0) {
TreeNode node = stack.pop();
result.add(node.val);
if (node.right != null){ // 以右節(jié)點(diǎn)為根坛怪，開始遞歸
ptr = node.right;
while (ptr != null) {
stack.push(ptr);
ptr = ptr.left;
}
}
}
return result;
}
}
先序遍歷
即遍歷順序?yàn)橄雀颍笥夜赡遥缟蠄D例子的順序即為：2,7,2,6,5,11,5,9,4袜匿。
遞歸算法思路也很直接，先輸出自身稚疹，然后遞歸輸出左子樹居灯，再遞歸輸出右子樹即可。
非遞歸算法思路和中序遍歷差不多内狗，參考遞歸的思路怪嫌，應(yīng)該先輸出自身，然后再把左節(jié)點(diǎn)全部入棧柳沙，循環(huán)到底岩灭，然后挨個(gè)出棧對(duì)右節(jié)點(diǎn)當(dāng)做一個(gè)根節(jié)點(diǎn)執(zhí)行類似遞歸的操作。
遞歸代碼
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
helper(root, res);
return res;
}
private void helper(TreeNode root, List<Integer> res) {
if (root == null) return;
res.add(root.val);
helper(root.left, res);
helper(root.right, res);
}
}
非遞歸代碼
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
TreeNode ptr = root;
List<Integer> result = new LinkedList<>();
Stack<TreeNode> stack = new Stack();
while (ptr != null) {
result.add(ptr.val);
stack.push(ptr);
ptr = ptr.left;
}
while (stack.size() != 0) {
TreeNode node = stack.pop();
if (node.right != null){
ptr = node.right;
while (ptr != null) {
result.add(ptr.val);
stack.push(ptr);
ptr = ptr.left;
}
}
}
return result;
}
}
后序遍歷
思路
后序遍歷即后跟順序：左右根赂鲤，上圖例中的二叉樹后序遍歷結(jié)果為：2,5,11,6,7,4,9,5,2
遞歸思路和上面兩種順序一樣噪径，先遞歸左子樹，再遞歸右子樹数初，再輸出自身即可找爱。
非遞歸稍稍復(fù)雜一點(diǎn)，和中序先序不同的地方在于泡孩，這個(gè)順序的左和右之間沒有指針相連缴允。把最左路線上的節(jié)點(diǎn)全部入棧之后，出棧一個(gè)有右子樹的左節(jié)點(diǎn)，不能直接輸出它而是得等其右子樹全部輸出完成之后才能輸出练般，所以我們需要再把這個(gè)節(jié)點(diǎn)扔進(jìn)去，但是怎么區(qū)分是第一次扔進(jìn)去的锈候，還是第二次扔進(jìn)去的呢薄料？如果區(qū)分不了就會(huì)死循環(huán)，兩種方式：
- 添加一塊其余的空間泵琳，比如 map摄职，或者在節(jié)點(diǎn)上加個(gè) Flag，來記憶
- 再取出一個(gè)節(jié)點(diǎn)的右子樹后获列，將其右子樹清空谷市，這樣遇到空右子樹的節(jié)點(diǎn)我們就直接輸出就好了，不過這樣的問題在于會(huì)破壞原始樹的結(jié)構(gòu)
遞歸代碼
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
helper(root, res);
return res;
}
private void helper(TreeNode root, List<Integer> res) {
if (root == null) return;
helper(root.left, res);
helper(root.right, res);
res.add(root.val);
}
}
非遞歸代碼
public List<Integer> postorderTraversal(TreeNode root) {
TreeNode ptr = root;
List<Integer> result = new LinkedList<>();
Stack<TreeNode> stack = new Stack();
while (ptr != null) {
stack.push(ptr);
ptr = ptr.left;
}
while (stack.size() != 0) {
TreeNode node = stack.pop();
if (node.right == null){
result.add(node.val);
continue;
}
ptr = node.right;
node.right = null; // 把根節(jié)點(diǎn)再扔回棧里面击孩，通過有無右子樹區(qū)分是第一次還是第二次入棧
stack.add(node);
while (ptr != null) {
stack.push(ptr);
ptr = ptr.left;
}
}
return result;
}
層次遍歷
思路
非遞歸的解法迫悠，思路很簡(jiǎn)單，通過隊(duì)列先入先出的特性來實(shí)現(xiàn)巩梢，從根節(jié)點(diǎn)出發(fā)创泄，輸出，左節(jié)點(diǎn)入隊(duì)括蝠，右節(jié)點(diǎn)入隊(duì)鞠抑，把下一層的節(jié)點(diǎn)取出來，輸出忌警，然后分別入隊(duì)左右節(jié)點(diǎn)搁拙，直到最后隊(duì)列空了，意味著到了底層法绵，遍歷完畢箕速。
還有一種深度優(yōu)先的遞歸解法，把層數(shù)傳下去礼烈，先根或者中根序遍歷時(shí)維護(hù)這一層的全局?jǐn)?shù)組即可弧满。
DFS 遞歸代碼
class Solution {
public List<List<Integer>> result = new LinkedList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
helper(0, root);
return result;
}
public void helper(int level, TreeNode root) {
if (root == null) {
return;
}
if (result.size() <= level) {
result.add(new LinkedList<>());
}
result.get(level).add(root.val);
helper(level + 1, root.left);
helper(level + 1, root.right);
}
}
BFS 非遞歸代碼
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new LinkedList<>();
if (root ==null){
return result;
}
List<TreeNode> list = new LinkedList<>();
list.add(root);
while (!list.isEmpty()) {
List<Integer> level = new LinkedList<>();
int size = list.size();
for (int i = 0; i < size; i++) { // 取出一層所有的節(jié)點(diǎn)
TreeNode node = list.remove(0);
level.add(node.val); // 輸出
if (node.left != null) {
list.add(node.left); // 左節(jié)點(diǎn)入隊(duì)，如果有的話
}
if (node.right != null) {
list.add(node.right); // 右節(jié)點(diǎn)入隊(duì)此熬，如果有的話
}
}
result.add(level);
}
return result;
}
}
之字形遍歷
這是層次遍歷的變種庭呜，想當(dāng)于層次遍歷的偶數(shù)層需要反序，所以我們只需要知道當(dāng)前層的奇偶即可犀忱。
以層次遍歷 BFS 的解法為基礎(chǔ)募谎，我們只需要加入如下一段即可：
if (result.size() % 2 == 1){ // 在加入結(jié)果前判斷一下已有長(zhǎng)度是不是奇數(shù)，是的話這一層就是偶數(shù)阴汇，反轉(zhuǎn)一下即可数冬。
Collections.reverse(level);
}
完整代碼：
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new LinkedList<>();
if (root ==null){
return result;
}
List<TreeNode> list = new LinkedList<>();
list.add(root);
while (!list.isEmpty()) {
List<Integer> level = new LinkedList<>();
int size = list.size();
for (int i = 0; i < size; i++) {
TreeNode node = list.remove(0);
if (node.left != null) {
list.add(node.left);
}
if (node.right != null) {
list.add(node.right);
}
level.add(node.val);
}
if (result.size() % 2 == 1){
Collections.reverse(level);
}
result.add(level);
}
return result;
}
}
