文章目錄
- 1. 前序周遊
- 2. 中序周遊
- 3. 後序周遊
- 4. 層序周遊
1. 前序周遊
Leetcode 144. 二叉樹的前序周遊
遞歸實作:
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);
}
}
疊代實作:沿左側分支展開,同時壓棧,直到左子樹為空;彈出棧頂元素,轉向右子樹,重複上述步驟,直到棧為空。該方法适用于三種周遊方式。
- 将目前節點壓入棧中,節點值加入輸出序列(前序周遊),跳轉到左子樹;
- 重複過程 1,直到左子樹為空;
- 彈出棧頂元素,節點值加入輸出序列(中序周遊),跳轉到右子樹;
- 重複過程 1,直到棧為空。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stk = new Stack<>();
while (true) {
while (root != null) {
res.add(root.val);
stk.push(root);
root = root.left;
}
if (stk.isEmpty()) {
break;
}
TreeNode node = stk.pop();
root = node.right;
}
return res;
}
}
疊代實作:每次循環,右子節點先入後出,左子節點後入先出,利用棧的特性完成周遊,僅适用于前序周遊。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stk = new Stack<>();
stk.push(root);
while (!stk.isEmpty()) {
TreeNode node = stk.pop();
res.add(node.val);
if (node.right != null) {
stk.push(node.right);
}
if (node.left != null) {
stk.push(node.left);
}
}
return res;
}
}
2. 中序周遊
Leetcode 94. 二叉樹的中序周遊
遞歸實作:
class Solution {
public List<Integer> inorderTraversal(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);
}
}
疊代實作:
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stk = new Stack<>();
while (true) {
while (root != null) {
stk.push(root);
root = root.left;
}
if (stk.isEmpty()) {
break;
}
TreeNode node = stk.pop();
res.add(node.val);
root = node.right;
}
return res;
}
}
3. 後序周遊
Leetcode 145. 二叉樹的後序周遊
遞歸實作:
class Solution {
public List<Integer> postorderTraversal(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);
}
}
疊代實作:後序周遊就是逆前序周遊的倒序輸出,逆前序周遊即先通路根節點,再處理右子樹,最後處理左子樹。
- 前序周遊:根 -> 左 -> 右;
- 逆前序周遊:根 -> 右 -> 左;
- 後序周遊:左 -> 右 -> 根。
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stk = new Stack<>();
while (true) {
while (root != null) {
res.add(root.val);
stk.push(root);
root = root.right;
}
if (stk.isEmpty()) {
break;
}
TreeNode node = stk.pop();
root = node.left;
}
Collections.reverse(res);
return res;
}
}
疊代實作:後序周遊中,隻有周遊完右子樹,才能通路根節點。是以,需要引入變量記錄上一次通路的節點,用于判斷是否完成了對右子樹的周遊。
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<Integer> res = new ArrayList<>();
Stack<TreeNode> stk = new Stack<>();
TreeNode pre = null;
while (root != null) {
pre = root;
stk.push(root);
root = root.left;
}
while (!stk.isEmpty()) {
TreeNode node = stk.peek();
if (pre == node.right || node.right == null) {
pre = stk.pop();
res.add(node.val);
} else {
root = node.right;
while (root != null) {
pre = root;
stk.push(root);
root = root.left;
}
}
}
return res;
}
}
4. 層序周遊
Leetcode 102. 二叉樹的層次周遊
遞歸實作:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
helper(root, 0, res);
return res;
}
private void helper(TreeNode root, int level, List<List<Integer>> res) {
if(root == null) {
return;
}
if(level == res.size()) {
res.add(new ArrayList<>());
}
res.get(level).add(root.val);
helper(root.left, level+1,res);
helper(root.right,level+1,res);
}
}
疊代實作:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
List<List<Integer>> res = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int n = queue.size();
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < n; i++) {
TreeNode node = queue.remove();
ans.add(node.val);
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
res.add(ans);
}
return res;
}
}