程式碼隨想錄 | 二叉樹的遍歷
二叉樹的遞歸遍歷
遞歸的三要素
1.遞歸函數的參數和返回值
2.遞歸出口
3.單層遞歸的邏輯
144. 二叉樹的前序遍歷
給你二叉樹的根節點 root ，返回它節點值的 前序 遍歷。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
preoder(root,result);
return result;
}
public void preoder(TreeNode node,List<Integer> result){
if (node==null){
return;
}
result.add(node.val);//前序遍歷：中、左、右
preoder(node.left,result);
preoder(node.right,result);
}
}
94. 二叉樹的中序遍歷
給定一個二叉樹的根節點 root ，返回 它的 中序 遍歷 。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList();
inorder(root,result);
return result;
}
public void inorder(TreeNode node, List<Integer> result){
if(node==null){
return;
}
inorder(node.left,result);//中序遍歷：左、中、右
result.add(node.val);
inorder(node.right,result);
}
}
145. 二叉樹的後序遍歷
給你一棵二叉樹的根節點 root ，返回其節點值的 後序遍歷 。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList();
postorder(root,result);
return result;
}
public void postorder(TreeNode node,List<Integer> result){
if(node==null){
return;
}
postorder(node.left,result);//後序遍歷：左、右、中
postorder(node.right,result);
result.add(node.val);
}
}
二叉樹的迭代遍歷
用棧操作，遞歸也是用棧實現的嘛🙂
144. 二叉樹的前序遍歷
給你二叉樹的根節點 root ，返回它節點值的 前序 遍歷。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();//結果列表
Stack<TreeNode> stack = new Stack<>();
if(root==null){
return result;
}
stack.push(root);//先把根節點加到棧中去
while (!stack.empty()){
TreeNode node = stack.pop();//從棧中彈出一個結點來進行操作
result.add(node.val);//彈出的元素加到結果列表中
if(node.right!=null){
stack.push(node.right);//右孩子不空就進棧
}
if(node.left!=null){
stack.push(node.left);//左孩子不空就進棧
}
}
return result;
}
}
- 妙蛙種子吃了妙脆角，妙到家啦
145. 二叉樹的後序遍歷
給你一棵二叉樹的根節點 root ，返回其節點值的 後序遍歷 。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();//結果列表
Stack<TreeNode> stack = new Stack<>();
if(root==null){
return result;
}
stack.push(root);//先把根節點加到棧中去
while (!stack.empty()){
TreeNode node = stack.pop();//從棧中彈出一個結點來進行操作
result.add(node.val);//彈出的元素加到結果列表中
if(node.left!=null){
stack.push(node.left);//左孩子不空就進棧
}
if(node.right!=null){
stack.push(node.right);//右孩子不空就進棧
}
}
Collections.reverse(result);
return result;
}
}
Collections.reverse(result) 鏈表反轉
- 這題和前序遍歷十分相似，就是入棧順序不一樣，畫圖找一下順序，改前序遍歷的程式碼就可啦
94. 二叉樹的中序遍歷
給定一個二叉樹的根節點 root ，返回 它的 中序 遍歷 。
- 中序遍歷和前序遍歷、後序遍歷不一樣的地方是，前序遍歷（中左右）、後序遍歷（左右中），中結點在兩端，處理結點就是當前遍歷的結點（從根節點開始遍歷，從根節點開始處理）。而中序遍歷的遍歷從根節點開始，要處理的結點卻是從最左側的結點開始。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();//結果列表
Stack<TreeNode> stack = new Stack<>();
if(root==null){
return result;
}
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.二叉樹的層序遍歷
給你二叉樹的根節點 root ，返回其節點值的 層序遍歷 。 （即逐層地，從左到右訪問所有節點）。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();//外層鏈表
Queue<TreeNode> que = new LinkedList<>();//新建一個隊列
if (root == null) {
return res;
}
que.add(root);//把根節點放入隊列
while (!que.isEmpty()){
//當隊列不為空時
ArrayList<Integer> item = new ArrayList<>();//內層鏈表
int size = que.size();//隊列的大小
while (size>0){
TreeNode node = que.poll();//彈出當前結點
if(node.left!=null){que.add(node.left);}//把當前結點的左孩子加進去（如果有的話）
if(node.right!=null){que.add(node.right);}//把當前結點的右孩子加進去（如果有的話）
item.add(node.val);//當前結點加到鏈表
size--;
}
res.add(item);//內層鏈表加入到外層鏈表中
}
return res;
}
}
下面是一堆層序遍歷的題
107. 二叉樹的層序遍歷 II
給你二叉樹的根節點 root ，返回其節點值 自底向上的層序遍歷 。 （即按從葉子節點所在層到根節點所在的層，逐層從左向右遍歷）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();//外層鏈表
Queue<TreeNode> que = new LinkedList<TreeNode>();//隊列
if(root==null)return res;
que.add(root);//把根結點放入隊列
while (!que.isEmpty()){
List<Integer> item = new ArrayList<>();
int size = que.size();
while (size > 0) {
TreeNode node = que.poll();//隊列中彈出一個結點
item.add(node.val);
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
size--;
}
res.add(item);
}
Collections.reverse(res);
return res;
}
}
199. 二叉樹的右視圖
給定一個二叉樹的 根節點 root，想像自己站在它的右側，按照從頂部到底部的順序，返回從右側所能看到的節點值。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> res = new ArrayList<>();
Queue<TreeNode> que = new LinkedList<>();
if(root==null)return res;
que.add(root);//根結點不為空，放入隊列
while (!que.isEmpty()){
List<Integer> item = new ArrayList<>();
int size = que.size();
while (size>0){
TreeNode node = que.poll();
item.add(node.val);
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
size--;
}
Integer i = item.get(item.size() - 1);
res.add(i);
}
return res;
}
}
637. 二叉樹的層平均值
給定一個非空二叉樹的根節點 root , 以數組的形式返回每一層節點的平均值。與實際答案相差 10-5 以內的答案可以被接受。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
Queue<TreeNode> que = new LinkedList<>();
if(root==null)return res;
que.add(root);
while (!que.isEmpty()){
int size = que.size();
double x = 0;
double sum = 0;
int count = size;
while (size>0){
TreeNode node = que.poll();
sum += node.val;
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
size--;
}
x = sum/count;
res.add(x);
}
return res;
}
}
429. N 叉樹的層序遍歷
給定一個 N 叉樹，返回其節點值的層序遍歷。（即從左到右，逐層遍歷）。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> res = new ArrayList<>();//外層鏈表
Queue<Node> que = new LinkedList<>();//新建一個隊列
if (root == null) {
return res;
}
que.add(root);//把根節點放入隊列
while (!que.isEmpty()){
//當隊列不為空時
ArrayList<Integer> item = new ArrayList<>();//內層鏈表
int size = que.size();//隊列的大小
while (size>0){
Node node = que.poll();//彈出當前結點
//當前結點加到鏈表
if(node.children!=null){
for (Node child : node.children) {
que.add(child);
}
}
item.add(node.val);
size--;
}
res.add(item);//內層鏈表加入到外層鏈表中
}
return res;
}
}
- 添加子結點到隊列的操作有點不一樣
515. 在每個樹行中找最大值
給定一棵二叉樹的根節點 root ，請找出該二叉樹中每一層的最大值。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> res = new ArrayList<>();
Queue<TreeNode> que = new LinkedList<>();
if(root==null){
return res;
}
que.add(root);
while(!que.isEmpty()){
int size = que.size();
int x = Integer.MIN_VALUE;
while(size>0){
TreeNode node = que.poll();
x = node.val>x ? node.val : x;
if(node.left!=null){que.add(node.left);}
if(node.right!=null){que.add(node.right);}
size--;
}
res.add(x);
}
return res;
}
}
116. 填充每個節點的下一個右側節點指針
給定一個 完美二叉樹 ，其所有葉子節點都在同一層，每個父節點都有兩個子節點。二叉樹定義如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個 next 指針，讓這個指針指向其下一個右側節點。如果找不到下一個右側節點，則將 next 指針設置為 NULL。
初始狀態下，所有 next 指針都被設置為 NULL。
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
Queue<Node> que = new LinkedList<>();
if (root == null) {
return root;
}
que.add(root);
while (que.size() > 0) {
int size = que.size();
Node node = que.poll();
if (node.left != null) {que.add(node.left);}
if (node.right != null) {que.add(node.right);}
for (int i = 1; i < size; i++) {
Node next = que.poll();//彈出該層剩餘元素
if (next.left != null) que.add(next.left);
if (next.right != null) que.add(next.right);
node.next = next;
node = next;
}
}
return root;
}
}
117. 填充每個節點的下一個右側節點指針 II
給定一個二叉樹
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每個 next 指針，讓這個指針指向其下一個右側節點。如果找不到下一個右側節點，則將 next 指針設置為 NULL。
初始狀態下，所有 next 指針都被設置為 NULL。
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, Node _left, Node _right, Node _next) {
val = _val;
left = _left;
right = _right;
next = _next;
}
};
*/
class Solution {
public Node connect(Node root) {
Queue<Node> que = new LinkedList<>();
if (root == null) {
return root;
}
que.add(root);
while (que.size() > 0) {
int size = que.size();
Node node = que.poll();
if (node.left != null) {que.add(node.left);}
if (node.right != null) {que.add(node.right);}
for (int i = 1; i < size; i++) {
Node next = que.poll();//彈出該層剩餘元素
if (next.left != null) que.add(next.left);
if (next.right != null) que.add(next.right);
node.next = next;
node = next;
}
}
return root;
}
}
- 離大譜，這題程式碼跟上題一樣，一模一樣
104. 二叉樹的最大深度
給定一個二叉樹，找出其最大深度。
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int maxDepth(TreeNode root) {
Queue<TreeNode> que = new LinkedList<>();//新建一個隊列
if (root == null) {
return 0;
}
que.add(root);//把根節點放入隊列
int count = 0;
while (!que.isEmpty()) {
//當隊列不為空時
count++;
ArrayList<Integer> item = new ArrayList<>();//內層鏈表
int size = que.size();//隊列的大小
while (size > 0) {
TreeNode node = que.poll();//彈出當前結點
if (node.left != null) {
que.add(node.left);
}//把當前結點的左孩子加進去（如果有的話）
if (node.right != null) {
que.add(node.right);
}//把當前結點的右孩子加進去（如果有的話）
size--;
}
}
return count;
}
}
111. 二叉樹的最小深度
給定一個二叉樹，找出其最小深度。
最小深度是從根節點到最近葉子節點的最短路徑上的節點數量。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public int minDepth(TreeNode root) {
Queue<TreeNode> que = new LinkedList<>();//新建一個隊列
if (root == null) {
return 0;
}
que.add(root);//把根節點放入隊列
int count = 0;
while (!que.isEmpty()) {
//當隊列不為空時
count++;
ArrayList<Integer> item = new ArrayList<>();//內層鏈表
int size = que.size();//隊列的大小
while (size > 0) {
TreeNode node = que.poll();//彈出當前結點
if (node.left != null) {
que.add(node.left);
}//把當前結點的左孩子加進去（如果有的話）
if (node.right != null) {
que.add(node.right);
}//把當前結點的右孩子加進去（如果有的話）
if(node.left==null&&node.right==null){
return count;
}
size--;
}
}
return count;
}
}
總結
-
通過今天的題目大致掌握二叉樹的結構。深度優先遍歷方面掌握前序、中序、後續的遞歸實現和迭代實現。掌握廣度優先遍歷的模板（寫了十道層序遍歷的題目，就算是小豬也會了😐
-
今天的題目自己寫出來的不多，除了最後幾道改模板的題，不知道是因為天太冷還是頭上戴的蝴蝶結封印了我的智慧的🙃
