靚仔靚女們大家好，：java小杰要加油围详，今天我來分享一篇關(guān)于二叉樹的文章（建議收藏朴乖，便于鞏固基礎(chǔ)）。
- 看完此文leetcode至少解決八道題
- 掌握二叉樹的前序助赞、中序买羞、后序遍歷以及兩種不同的實(shí)現(xiàn)方式：遞歸與非遞歸
- 非遞歸時(shí)遍歷與層次遍歷時(shí)，有詳細(xì)的圖解表示隊(duì)列/棧中的元素是如何移動(dòng)的雹食，有助于理解代碼的運(yùn)行
二叉樹介紹
二叉樹（binary tree） 是指樹中節(jié)點(diǎn)的度不大于2的有序樹畜普，它是一種最簡單且最重要的樹。
二叉樹的遞歸定義為： 二叉樹是一棵空樹群叶，或者是一棵由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的吃挑，分別稱作根的左子樹和右子樹組成的非空樹；左子樹和右子樹又同樣都是二叉樹
- 邏輯上二叉樹有五種基本形態(tài)街立，如圖所示
- 空二叉樹
- 只有一個(gè)根結(jié)點(diǎn)的二叉樹
- 只有左子樹
- 完全二叉樹
- 只有右子樹
image
二叉樹相關(guān)屬性解釋：
- 結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向子樹分支的信息舶衬。
- 結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)擁有子樹的數(shù)目稱為結(jié)點(diǎn)的度。
- 葉子結(jié)點(diǎn)：也稱為終端結(jié)點(diǎn)赎离，沒有子樹的結(jié)點(diǎn)或者度為零的結(jié)點(diǎn)逛犹。
- 分支結(jié)點(diǎn)：也稱為非終端結(jié)點(diǎn)，度不為零的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)梁剔。
- 樹的度：樹中所有結(jié)點(diǎn)的度的最大值虽画。
- 結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開始，假設(shè)根結(jié)點(diǎn)為第1層荣病，根結(jié)點(diǎn)的子節(jié)點(diǎn)為第2層码撰，依此類推，如果某一個(gè)結(jié)點(diǎn)位于第L層个盆，則其子節(jié)點(diǎn)位于第L+1層脖岛。
- 樹的深度：也稱為樹的高度，樹中所有結(jié)點(diǎn)的層次最大值稱為樹的深度颊亮。
- 有序樹：如果樹中各棵子樹的次序是有先后次序鸡岗，則稱該樹為有序樹。
- 無序樹：如果樹中各棵子樹的次序沒有先后次序编兄，則稱該樹為無序樹轩性。
二叉樹遍歷方式
- 二叉樹遍歷方式分為三種
- 前序遍歷（根左右）： 訪問根結(jié)點(diǎn)，再訪問左子樹、再訪問右子樹揣苏。
- 中序遍歷（左根右）： 先訪問左子樹悯嗓，再訪問根結(jié)點(diǎn)、再訪問右子樹卸察。
- 后續(xù)遍歷（左右根）： 先訪問左子樹脯厨，再訪問右子樹，再訪問根結(jié)點(diǎn)坑质。
例如一個(gè)這個(gè)樣子的二叉樹合武，按三種遍歷方法分別遍歷，輸出的結(jié)果分別是
image
- 前序遍歷： ABDECFG
- 中序遍歷： DBEAFCG
- 后續(xù)遍歷： DEBFGCA
下面我們一起來用代碼實(shí)現(xiàn)下這三種遍歷
- 注：以上前序涡扼、中序稼跳、后序每一種遍歷方式都有遞歸和非遞歸兩種實(shí)現(xiàn)方法
- 前序遍歷就是深度優(yōu)先遍歷（DFS）
- 層次遍歷就是廣度優(yōu)先遍歷（BFS）
二叉樹遞歸遍歷
class Solution {
//聲明列表
ArrayList<Integer> list = new ArrayList<>();
public List<Integer> preorderTraversal(TreeNode root) {
// 如果根節(jié)點(diǎn)為空，則直接返回空列表
if (root == null){
return new ArrayList<>();
}
//節(jié)點(diǎn)不為空吃沪，將節(jié)點(diǎn)的值添加進(jìn)列表中
list.add(root.val);
//判斷此節(jié)點(diǎn)的左節(jié)點(diǎn)是否為空汤善，如果不為空則將遞歸遍歷左子樹
if (root.left != null){
preorderTraversal(root.left);
}
//判斷此節(jié)點(diǎn)的右節(jié)點(diǎn)是否為空，如果不為空則將遞歸遍歷右子樹
if (root.right != null){
preorderTraversal(root.right);
}
//最后返回列表
return list;
}
}
class Solution {
//聲明列表
ArrayList<Integer> list = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
// 如果根節(jié)點(diǎn)為空票彪，則直接返回空列表
if (root == null){
return new ArrayList<>();
}
//判斷此節(jié)點(diǎn)的左節(jié)點(diǎn)是否為空红淡，如果不為空則將遞歸遍歷此節(jié)點(diǎn)的左子樹
if (root.left != null){
inorderTraversal(root.left);
}
//節(jié)點(diǎn)不為空，將節(jié)點(diǎn)的值添加進(jìn)列表中
list.add(root.val);
//判斷此節(jié)點(diǎn)的右節(jié)點(diǎn)是否為空降铸，如果不為空則將遞歸遍歷此節(jié)點(diǎn)的右子樹
if (root.right != null){
inorderTraversal(root.right);
}
//最后返回列表
return list;
}
}
class Solution {
//聲明列表
ArrayList<Integer> list = new ArrayList<>();
public List<Integer> postorderTraversal(TreeNode root) {
// 如果根節(jié)點(diǎn)為空在旱，則直接返回空列表
if (root == null){
return new ArrayList<>();
}
//判斷此節(jié)點(diǎn)的左節(jié)點(diǎn)是否為空，如果不為空則將遞歸遍歷此節(jié)點(diǎn)的左子樹
if (root.left != null){
postorderTraversal(root.left);
}
//判斷此節(jié)點(diǎn)的右節(jié)點(diǎn)是否為空推掸，如果不為空則將遞歸遍歷此節(jié)點(diǎn)的右子樹
if (root.right != null){
postorderTraversal(root.right);
}
//節(jié)點(diǎn)不為空桶蝎，將節(jié)點(diǎn)的值添加進(jìn)列表中
list.add(root.val);
//最后返回列表
return list;
}
}
我們通過觀察發(fā)現(xiàn)，這代碼怎么這么像终佛，是的就是很像滑蚯，他們唯一的區(qū)別就是list.add(root.val);代碼的位置不一樣达址，這行代碼就代表文中的 遍歷（訪問）
下圖中為前序遍歷（根左右）
image
下圖中為中序遍歷（左根右）
image
下圖中為后序遍歷（左右根）
image
二叉樹非遞歸遍歷
- 用到棧（FILO 先進(jìn)后出的特性）
- 每段代碼后，都有棧和其中元素的關(guān)系具體過程歇式，建議靜下心來慢慢看芯咧，有助于理解代碼如何運(yùn)行
- 前序遍歷
class Solution {
List list = new ArrayList();
public List<Integer> preorderTraversal(TreeNode root) {
//如果根節(jié)點(diǎn)為空牙捉，則直接返回空列表
if(root==null){
return new ArrayList();
}
//聲明一個(gè)棧
Stack<TreeNode> stack = new Stack<>();
//將節(jié)點(diǎn)入棧
stack.push(root);
//如果棧不為空
while (!stack.empty()){
//從棧彈出這個(gè)節(jié)點(diǎn)
TreeNode node = stack.pop();
//添加進(jìn)列表中
list.add(node.val);
// 如果這個(gè)節(jié)點(diǎn)的右子節(jié)點(diǎn)不為空
if (node.right!=null){
// 將其入棧 因?yàn)闂Ｊ窍冗M(jìn)后出，所以先壓棧右子節(jié)點(diǎn) 后出
stack.push(node.right);
}
// 如果這個(gè)節(jié)點(diǎn)的左子節(jié)點(diǎn)不為空
if (node.left!=null){
// 將其入棧 因?yàn)闂Ｊ窍冗M(jìn)后出敬飒，所以后壓棧左子節(jié)點(diǎn) 先出
}
}
//返回列表
return list;
}
}
image
image
- 中序遍歷
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
//判斷節(jié)點(diǎn)是否為空邪铲，為空的話直接返回空列表
if (root == null){
return new ArrayList();
}
//聲明列表存儲(chǔ)結(jié)果
List<Integer> list = new ArrayList();
//聲明一個(gè)棧
Stack<TreeNode> stack = new Stack<>();
//當(dāng)節(jié)點(diǎn)不為空或者棧不為空時(shí)
while (root != null || !stack.empty()){
//當(dāng)節(jié)點(diǎn)不為空時(shí)
while (root != null){
//將節(jié)點(diǎn)壓棧
stack.push(root);
//將節(jié)點(diǎn)指向其左子節(jié)點(diǎn)
root = root.left;
}
//如果棧不為空
if (!stack.empty()){
//將棧里元素彈出來
TreeNode node = stack.pop();
//添加進(jìn)列表中
list.add(node.val);
//將節(jié)點(diǎn)指向其右子節(jié)點(diǎn)
root = node.right;
}
}
return list;
}
}
image
image
- 后序遍歷
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
// 如果根節(jié)點(diǎn)為空，則直接返回空列表
if (root == null){
return new ArrayList<>();
}
//聲明列表
ArrayList<Integer> list = new ArrayList<>();
//聲明棧A
Stack<TreeNode> stackA = new Stack<TreeNode>();
//聲明棧B
Stack<TreeNode> stackB = new Stack<TreeNode>();
//將次元素壓入棧A
stackA.push(root);
//當(dāng)棧A不為空時(shí)
while (!stackA.empty()){
//取出其中壓入的元素
TreeNode node = stackA.pop();
//壓入棧B中
stackB.push(node);
//當(dāng)此節(jié)點(diǎn)左子節(jié)點(diǎn)不為空時(shí)
if (node.left != null){
//壓入棧A
stackA.push(node.left);
}
//當(dāng)此節(jié)點(diǎn)右子節(jié)點(diǎn)不為空時(shí)
if (node.right != null){
//壓入棧A
stackA.push(node.right);
}
}
//當(dāng)棧B不為空時(shí)
while (!stackB.empty()){
//取出其元素并且添加至列表中
TreeNode node = stackB.pop();
list.add(node.val);
}
//最后返回列表
return list;
}
}
image
image
二叉樹層序遍歷（BFS）
- LeetCode 102 二叉樹的層序遍歷
- 用到隊(duì)列（FIFO 先進(jìn)先出的特性）代碼后有隊(duì)列和其中元素的關(guān)系具體過程无拗，建議靜下心來慢慢看带到，有助于理解代碼如何運(yùn)行
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<List<Integer>>();
}
// 聲明一個(gè)列表存儲(chǔ)每一行的數(shù)據(jù)
List<List<Integer>> result = new ArrayList<>();
//聲明一個(gè)隊(duì)列
LinkedList<TreeNode> queue = new LinkedList<>();
//如果根節(jié)點(diǎn)不為空，將其入隊(duì)
queue.offer(root);
//當(dāng)隊(duì)列不為空時(shí)英染，代表隊(duì)列里有數(shù)據(jù)
while (!queue.isEmpty()) {
//存儲(chǔ)每一行的數(shù)據(jù)line
List<Integer> line = new ArrayList<Integer>();
//保存隊(duì)列中現(xiàn)有數(shù)據(jù)的個(gè)數(shù)揽惹，這些就是要添加至每一行列表的值
int size = queue.size();
for (int i=0;i<size;i++){
//取出隊(duì)列的節(jié)點(diǎn) （FIFO 先進(jìn)先出）
TreeNode node = queue.poll();
line.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(line);
}
return result;
}
}
image
leetcode二叉樹相關(guān)練習(xí)
- 我們看到了這里被饿，對(duì)二叉樹的前序（DFS）、中序搪搏、后序狭握、遞歸/非遞歸以及層次遍歷(BFS)都有了一定的了解（如果上面的圖都消化了的話）
然后我們趁熱打鐵來幾道leetcode題目試試手！（總體代碼和上面只有稍微的改動(dòng)疯溺，因?yàn)榇笾滤枷胧且粯拥穆勐焉厦娴膬?nèi)容都消化了的話就很簡單啦）
class Solution {
public List<String> binaryTreePaths(TreeNode root) {
if (root == null){
return new ArrayList<>();
}
ArrayList<String> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<TreeNode>();
//這個(gè)棧存儲(chǔ)路徑，與上一個(gè)存儲(chǔ)節(jié)點(diǎn)的棧一樣的操作
Stack<String> path = new Stack<String>();
stack.push(root);
path.push(root.val+"");
while (!stack.empty()){
TreeNode node = stack.pop();
String p = path.pop();
//當(dāng)是葉子節(jié)點(diǎn)的時(shí)候囱嫩，此時(shí)棧中的路徑即為一條完整的路徑恃疯，可以加入到結(jié)果中
if (node.right == null && node.left == null ){
list.add(p);
}
//如果右子節(jié)點(diǎn)不為空
if (node.right != null){
stack.push(node.right);
//將臨時(shí)路徑繼續(xù)壓棧
path.push(p+"->"+node.right.val);
}
//如果左子節(jié)點(diǎn)不為空
if (node.left != null){
stack.push(node.left);
//將臨時(shí)路徑繼續(xù)壓棧
path.push(p+"->"+node.left.val);
}
}
return list;
}
}
class Solution {
public int maxDepth(TreeNode root) {
if (root == null){
return 0;
}
LinkedList<TreeNode> queue = new LinkedList<>();
int result = 0;
queue.offer(root);
while (!queue.isEmpty()){
//層數(shù)+1
result++;
//這是當(dāng)前層的節(jié)點(diǎn)的個(gè)數(shù)
int size = queue.size();
for (int i=0;i<size;i++){
//要將其全部出隊(duì)后，才可以再次計(jì)數(shù)
TreeNode node = queue.poll();
if (node.left != null){
//如果出隊(duì)的節(jié)點(diǎn)還有左子節(jié)點(diǎn)挠说，就入隊(duì)
queue.offer(node.left);
}
if (node.right != null){
//如果出隊(duì)的節(jié)點(diǎn)還有右子節(jié)點(diǎn)澡谭，就入隊(duì)
queue.offer(node.right);
}
}
}
//返回層數(shù)
return result;
}
}
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
if (root == null){
return new ArrayList<List<Integer>>() ;
}
List<List<Integer>> result = new ArrayList<List<Integer>>() ;
LinkedList<TreeNode> queue = new LinkedList<>();
//聲明一個(gè)棧，用來存儲(chǔ)每一層的節(jié)點(diǎn)
Stack<ArrayList<Integer> > stack = new Stack<>();
queue.offer(root);
while (!queue.isEmpty()){
int size = queue.size();
ArrayList<Integer> list = new ArrayList<>();
for (int i=0;i<size;i++){
TreeNode node = queue.poll();
list.add(node.val);
if (node.left != null){
queue.offer(node.left);
}
if (node.right != null){
queue.offer(node.right);
}
}
//將這一層的節(jié)點(diǎn)壓入棧中
stack.push(list);
}
//當(dāng)棧不為空時(shí)损俭，彈出結(jié)果蛙奖，從而達(dá)到從下往上遍歷二叉樹的效果
while (!stack.isEmpty()){
ArrayList<Integer> list = stack.pop();
result.add(list);
}
return result;
}
}
總結(jié)
我們通過這篇文章，至少可以解決leetcode上以下幾道題目
絮絮叨叨
如果大家覺得這篇文章對(duì)自己有一點(diǎn)點(diǎn)幫助的話杆兵，歡迎關(guān)注此號(hào) java小杰要加油
若文章有誤歡迎指出雁仲，靚仔靚女們，我們下篇文章見琐脏，關(guān)注我攒砖，開啟我們的故事
