代碼隨想錄——第十三天

第六章二叉樹part01

理論基礎

需要了解二叉樹的種類，存儲方式，遍歷方式以及二叉樹的定義

文章講解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html?

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;

? ? }

}

遞歸遍歷（必須掌握）

二叉樹的三種遞歸遍歷掌握其規(guī)律后声旺，其實很簡單

題目鏈接/文章講解/視頻講解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%80%92%E5%BD%92%E9%81%8D%E5%8E%86.html?

前序：

class Solution {

? ? public List<Integer> preorderTraversal(TreeNode root) {

? ? ? ? List<Integer> list = new ArrayList<>();

? ? ? ? traversal(root, list);

? ? ? ? return list; ? ?

? ? }

? ? public void traversal(TreeNode root, List<Integer> list){

? ? ? ? if(root == null){

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? list.add(root.val);

? ? ? ? // traversal(root, list);當前做操作就行?

? ? ? ? traversal(root.left, list);

? ? ? ? traversal(root.right, list);

? ? }

}

后序：

class Solution {

? ? public List<Integer> postorderTraversal(TreeNode root) {

? ? ? ? List<Integer> list = new ArrayList<>();

? ? ? ? traversal(root, list);

? ? ? ? return list;

? ? }

? ? public void traversal(TreeNode root, List<Integer> list){

? ? ? ? if(root == null){

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? traversal(root.left, list);

? ? ? ? traversal(root.right, list);

? ? ? ? list.add(root.val);

? ? }

}

中序：

class Solution {

? ? public List<Integer> inorderTraversal(TreeNode root) {

? ? ? ? List<Integer> list = new ArrayList<>();

? ? ? ? traversal(root, list);

? ? ? ? return list;

? ? }

? ? public void traversal(TreeNode root, List<Integer> list){

? ? ? ? if(root == null){

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? traversal(root.left, list);

? ? ? ? list.add(root.val);

? ? ? ? traversal(root.right, list);

? ? }

}

迭代遍歷（基礎不好的錄友唯咬，迭代法可以放過）

題目鏈接/文章講解/視頻講解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E8%BF%AD%E4%BB%A3%E9%81%8D%E5%8E%86.html?

錯誤前序遍歷：

class Solution {

? ? public List<Integer> inorderTraversal(TreeNode root) {

? ? ? ? List<Integer> list = new ArrayList<>();

? ? ? ? traversal(root, list);

? ? ? ? return list;

? ? }

? ? public void traversal(TreeNode root, List<Integer> list){

? ? ? ? if(root == null){

? ? ? ? ? ? return;

? ? ? ? }

? ? ? ? traversal(root.left, list);

? ? ? ? list.add(root.val);

? ? ? ? traversal(root.right, list);

? ? }

}

class Solution {

? ? public List<Integer> preorderTraversal(TreeNode root) {

? ? ? ? Deque<TreeNode> deq = new LinkedList<>();

? ? ? ? List<Integer> list = new ArrayList<>();

? ? ? ? deq.push(root);

? ? ? ? if (root == null) {

? ? ? ? ? ? return list;

? ? ? ? }// 特殊情況的判斷

? ? ? ? while(!deq.isEmpty()){

? ? ? ? ? ? TreeNode cur = deq.poll();

? ? ? ? ? ? list.add(cur.val);

? ? ? ? ? ? if(cur.right != null){

? ? ? ? ? ? ? ? deq.push(cur.right);

? ? ? ? ? ? }

? ? ? ? ? ? if(cur.left != null){

? ? ? ? ? ? ? ? deq.push(cur.left);

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return list;

? ? }

}

后序遍歷：

class Solution {

? ? public List<Integer> postorderTraversal(TreeNode root) {

? ? ? ? Deque<TreeNode> deq = new LinkedList<>();

? ? ? ? ArrayList<Integer> list = new ArrayList<>();

? ? ? ? deq.push(root);

? ? ? ? if (root == null) {

? ? ? ? ? ? return list;

? ? ? ? }

? ? ? ? while(!deq.isEmpty()){

? ? ? ? ? ? TreeNode cur = deq.poll();

? ? ? ? ? ? list.add(cur.val);

? ? ? ? ? ? if(cur.left != null){

? ? ? ? ? ? ? ? deq.push(cur.left);

? ? ? ? ? ? }

? ? ? ? ? ? if(cur.right != null){

? ? ? ? ? ? ? ? deq.push(cur.right);

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? Collections.reverse(list);

? ? ? ? return list;

? ? }

}

class Solution {

? ? public List<Integer> inorderTraversal(TreeNode root) {

? ? ? ? Deque<TreeNode> deq = new LinkedList<>();

? ? ? ? ArrayList<Integer> list = new ArrayList<>();

? ? ? ? TreeNode cur = root;

? ? ? ? while(!deq.isEmpty() || cur != null){

? ? ? ? ? ? if(cur != null){

? ? ? ? ? ? ? ? deq.push(cur);

? ? ? ? ? ? ? ? cur = cur.left;

? ? ? ? ? ? }else{

? ? ? ? ? ? ? ? cur = deq.pop();

? ? ? ? ? ? ? ? list.add(cur.val);

? ? ? ? ? ? ? ? cur = cur.right;

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return list;

? ? }

}

統(tǒng)一迭代（基礎不好的錄友，迭代法可以放過）

這是統(tǒng)一迭代法的寫法咬崔，如果學有余力税稼，可以掌握一下略

題目鏈接/文章講解：https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.html

class Solution {

public List<Integer> inorderTraversal(TreeNode root) {

? ? ? ? List<Integer> result = new LinkedList<>();

? ? Stack<TreeNode> st = new Stack<>();

? ? if (root != null) st.push(root);

? ? while (!st.empty()) {

? ? ? ? TreeNode node = st.peek();

? ? ? ? if (node != null) {

? ? ? ? ? ? st.pop(); // 將該節(jié)點彈出，避免重復操作垮斯，下面再將右中左節(jié)點添加到棧中

? ? ? ? ? ? if (node.right!=null) st.push(node.right); ?// 添加右節(jié)點（空節(jié)點不入棧）

? ? ? ? ? ? st.push(node); ? ? ? ? ? ? ? ? ? ? ? ? ?// 添加中節(jié)點

? ? ? ? ? ? st.push(null); // 中節(jié)點訪問過郎仆，但是還沒有處理，加入空節(jié)點做為標記兜蠕。

? ? ? ? ? ? if (node.left!=null) st.push(node.left); ? ?// 添加左節(jié)點（空節(jié)點不入棧）

? ? ? ? } else { // 只有遇到空節(jié)點的時候扰肌，才將下一個節(jié)點放進結果集

? ? ? ? ? ? st.pop(); ? ? ? ? ? // 將空節(jié)點彈出

? ? ? ? ? ? node = st.peek(); ? ?// 重新取出棧中元素

? ? ? ? ? ? st.pop();

? ? ? ? ? ? result.add(node.val); // 加入到結果集

? ? ? ? }

? ? }

? ? return result;

}

層序遍歷

看完本篇可以一口氣刷十道題，試一試熊杨，層序遍歷并不難曙旭，大家可以很快刷了十道題。

題目鏈接/文章講解/視頻講解：https://programmercarl.com/0102.%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E5%B1%82%E5%BA%8F%E9%81%8D%E5%8E%86.html

class Solution {

? ? public List<List<Integer>> levelOrder(TreeNode root) {

? ? ? ? List<List<Integer>> list = new ArrayList<>();

? ? ? ? Deque<TreeNode> deq = new LinkedList<>();

? ? ? ? if(root != null){

? ? ? ? ? ? deq.addLast(root);

? ? ? ? }

? ? ? ? while(!deq.isEmpty()){

? ? ? ? ? ? int size = deq.size();

? ? ? ? ? ? List<Integer> lt = new ArrayList<>();

? ? ? ? ? ? int i = 0;

? ? ? ? ? ? while(i < size){

? ? ? ? ? ? ? ? TreeNode cur = deq.removeFirst();

? ? ? ? ? ? ? ? lt.add(cur.val);

? ? ? ? ? ? ? ? if(cur.left != null){deq.addLast(cur.left);}

? ? ? ? ? ? ? ? if(cur.right != null){deq.addLast(cur.right);}

? ? ? ? ? ? ? ? i ++;

? ? ? ? ? ? }

? ? ? ? ? ? list.add(lt);

? ? ? ? }

? ? ? ? return list;

? ? }

}

反序層次遍歷：

? ? ? ? List<List<Integer>> rlist = new ArrayList<>();

? ? ? ? for(int i = list.size() - 1; i >= 0; i --){

? ? ? ? ? ? rlist.add(list.get(i));

? ? ? ? }

? ? ? ? return rlist;? ??

? Collections.reverse(list);//返回值是空在原集合上進行的操作

右視圖：

? ? ? ? List<Integer> res = new ArrayList<>();

? ? ? ? for(List<Integer> l : list){

? ? ? ? ? ? int size = l.size();

? ? ? ? ? ? res.add(l.get(size-1));

? ? ? ? }

? ? ? ? return res;

平均值：

class Solution {

? ? public List<Double> averageOfLevels(TreeNode root) {

? ? ? ? List<Double> result = new ArrayList<>();

? ? ? ? Deque<TreeNode> deq = new LinkedList<>();

? ? ? ? if(root != null){

? ? ? ? ? ? deq.addLast(root);

? ? ? ? }

? ? ? ? while(!deq.isEmpty()){

? ? ? ? ? ? int size = deq.size();

? ? ? ? ? ? List<Integer> lt = new ArrayList<>();

? ? ? ? ? ? int i = 0;

? ? ? ? ? ? double count = 0;

? ? ? ? ? ? while(i < size){

? ? ? ? ? ? ? ? TreeNode cur = deq.removeFirst();

? ? ? ? ? ? ? ? lt.add(cur.val);

? ? ? ? ? ? ? ? count += cur.val;

? ? ? ? ? ? ? ? if(i == size - 1){

? ? ? ? ? ? ? ? ? ? result.add(count / size);

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? if(cur.left != null){deq.addLast(cur.left);}

? ? ? ? ? ? ? ? if(cur.right != null){deq.addLast(cur.right);}

? ? ? ? ? ? ? ? i ++;

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return result;

? ? }

}

n叉樹

class Solution {

? ? public List<List<Integer>> levelOrder(Node root) {

? ? ? ? List<List<Integer>> list = new ArrayList<>();

? ? ? ? Deque<Node> deq = new LinkedList<>();

? ? ? ? if(root != null){

? ? ? ? ? ? deq.addLast(root);

? ? ? ? }

? ? ? ? while(!deq.isEmpty()){

? ? ? ? ? ? int size = deq.size();

? ? ? ? ? ? List<Integer> lt = new ArrayList<>();

? ? ? ? ? ? int i = 0;

? ? ? ? ? ? while(i < size){

? ? ? ? ? ? ? ? Node cur = deq.removeFirst();

? ? ? ? ? ? ? ? lt.add(cur.val);

? ? ? ? ? ? ? ? for(Node node : cur.children){

? ? ? ? ? ? ? ? ? ? if(node != null){deq.addLast(node);}

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? i ++;

? ? ? ? ? ? }

? ? ? ? ? ? list.add(lt);

? ? ? ? }

? ? ? ? return list; ? ?

? ? }

}

每層最小值：

class Solution {

? ? public List<Integer> largestValues(TreeNode root) {

? ? ? ? List<Integer> list = new ArrayList<>();

? ? ? ? Deque<TreeNode> deq = new LinkedList<>();

? ? ? ? if (root != null) {

? ? ? ? ? ? deq.addLast(root);

? ? ? ? }

? ? ? ? while (!deq.isEmpty()) {

? ? ? ? ? ? int size = deq.size();

? ? ? ? ? ? int max = Integer.MIN_VALUE;

? ? ? ? ? ? for (int i = 0; i < size; i++) {

? ? ? ? ? ? ? ? TreeNode cur = deq.removeFirst();

? ? ? ? ? ? ? ? if (cur.val > max) max = cur.val;

? ? ? ? ? ? ? ? if (cur.left != null) deq.addLast(cur.left);

? ? ? ? ? ? ? ? if (cur.right != null) deq.addLast(cur.right);

? ? ? ? ? ? }

? ? ? ? ? ? list.add(max);

? ? ? ? }

? ? ? ? return list;

? ? }

}

完美二叉樹指針：

class Solution {

? ? public Node connect(Node root) {

? ? ? ? Deque<Node> deq = new LinkedList<>();

? ? ? ? if (root != null) {

? ? ? ? ? ? deq.addLast(root);

? ? ? ? }

? ? ? ? while (!deq.isEmpty()) {

? ? ? ? ? ? int size = deq.size();

? ? ? ? ? ? List<Node> lt = new ArrayList<>();

? ? ? ? ? ? for (int i = 0; i < size; i++) {

? ? ? ? ? ? ? ? Node cur = deq.removeFirst();

? ? ? ? ? ? ? ? lt.add(cur);

? ? ? ? ? ? ? ? if (cur.left != null) deq.addLast(cur.left);

? ? ? ? ? ? ? ? if (cur.right != null) deq.addLast(cur.right);

? ? ? ? ? ? }

? ? ? ? ? ? lt.add(null);

? ? ? ? ? ? for(int i = 0; i < lt.size() - 1; i ++){

? ? ? ? ? ? ? ? lt.get(i).next = lt.get(i + 1);

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? return root; ? ? ?

? ? }

}

最大深度

class Solution {

? ? public int maxDepth(TreeNode root) {

? ? ? ? int deep = 0;

? ? ? ? Deque<TreeNode> deq = new LinkedList<>();

? ? ? ? if (root != null) {

? ? ? ? ? ? deq.addLast(root);

? ? ? ? }

? ? ? ? while (!deq.isEmpty()) {

? ? ? ? ? ? int size = deq.size();

? ? ? ? ? ? for (int i = 0; i < size; i++) {

? ? ? ? ? ? ? ? TreeNode cur = deq.removeFirst();

? ? ? ? ? ? ? ? if (cur.left != null) deq.addLast(cur.left);

? ? ? ? ? ? ? ? if (cur.right != null) deq.addLast(cur.right);

? ? ? ? ? ? }

? ? ? ? ? ? deep ++;

? ? ? ? }

? ? ? ? return deep;

? ? }

}

最小深度：

class Solution {

? ? public int minDepth(TreeNode root) {

? ? ? ? int deep = 0;

? ? ? ? boolean flag = false;

? ? ? ? Deque<TreeNode> deq = new LinkedList<>();

? ? ? ? if (root != null) {

? ? ? ? ? ? deq.addLast(root);

? ? ? ? }

? ? ? ? while (!deq.isEmpty()) {

? ? ? ? ? ? int size = deq.size();

? ? ? ? ? ? for (int i = 0; i < size; i++) {

? ? ? ? ? ? ? ? TreeNode cur = deq.removeFirst();

? ? ? ? ? ? ? ? if (cur.left == null && cur.right == null){

? ? ? ? ? ? ? ? ? ? flag = true;

? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? if (cur.left != null) deq.addLast(cur.left);

? ? ? ? ? ? ? ? if (cur.right != null) deq.addLast(cur.right);

? ? ? ? ? ? }

? ? ? ? ? ? deep ++;

? ? ? ? ? ? if(flag) break;

? ? ? ? }

? ? return deep;

? ? }

}

最后編輯于：2024.08.17 17:01:55

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者

人面猴
序言：七十年代末晶府，一起剝皮案震驚了整個濱河市桂躏，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌川陆，老刑警劉巖剂习，帶你破解...
沈念sama閱讀 212,816評論 6贊 492
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異书劝，居然都是意外死亡进倍，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 90,729評論 3贊 385
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門购对，熙熙樓的掌柜王于貴愁眉苦臉地迎上來猾昆，“玉大人，你說我怎么就攤上這事骡苞〈刮希” “怎么了？”我有些...
開封第一講書人閱讀 158,300評論 0贊 348
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵解幽，是天一觀的道長贴见。經(jīng)常有香客問我，道長躲株，這世上最難降的妖魔是什么片部？我笑而不...
開封第一講書人閱讀 56,780評論 1贊 285
?港島之戀（遺憾婚禮）
正文為了忘掉前任，我火速辦了婚禮霜定，結果婚禮上档悠，老公的妹妹穿的比我還像新娘廊鸥。我一直安慰自己，他們只是感情好辖所，可當我...
茶點故事閱讀 65,890評論 6贊 385
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布惰说。她就那樣靜靜地躺著，像睡著了一般缘回。火紅的嫁衣襯著肌膚如雪吆视。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 50,084評論 1贊 291
城市分裂傳說
那天酥宴，我揣著相機與錄音啦吧，去河邊找鬼。笑死幅虑，一個胖子當著我的面吹牛丰滑，可吹牛的內容都是我干的。我是一名探鬼主播倒庵，決...
沈念sama閱讀 39,151評論 3贊 410
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼褒墨，長吁一口氣：“原來是場噩夢啊……” “哼！你這毒婦竟也來了擎宝？” 一聲冷哼從身側響起郁妈，我...
開封第一講書人閱讀 37,912評論 0贊 268
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤，失蹤者是張志新（化名）和其女友劉穎绍申，沒想到半個月后噩咪，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 44,355評論 1贊 303
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡极阅，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內容為張勛視角年9月15日...
茶點故事閱讀 36,666評論 2贊 327
?白月光啟示錄
正文我和宋清朗相戀三年胃碾，在試婚紗的時候發(fā)現(xiàn)自己被綠了。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片筋搏。...
茶點故事閱讀 38,809評論 1贊 341
活死人
序言：一個原本活蹦亂跳的男人離奇死亡仆百，死狀恐怖，靈堂內的尸體忽然破棺而出奔脐，到底是詐尸還是另有隱情俄周，我是刑警寧澤，帶...
沈念sama閱讀 34,504評論 4贊 334
?日本核電站爆炸內幕
正文年R本政府宣布髓迎，位于F島的核電站峦朗，受9級特大地震影響，放射性物質發(fā)生泄漏排龄。R本人自食惡果不足惜波势，卻給世界環(huán)境...
茶點故事閱讀 40,150評論 3贊 317
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧艰亮，春花似錦闭翩、人聲如沸挣郭。這莊子的主人今日做“春日...
開封第一講書人閱讀 30,882評論 0贊 21
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽兑障。三九已至侄非，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間流译，已是汗流浹背逞怨。一陣腳步聲響...
開封第一講書人閱讀 32,121評論 1贊 267
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留福澡，地道東北人叠赦。一個月前我還...
沈念sama閱讀 46,628評論 2贊 362
代替公主和親
正文我出身青樓，卻偏偏與公主長得像革砸，于是被迫代替她去往敵國和親除秀。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當晚...
茶點故事閱讀 43,724評論 2贊 351

代碼隨想錄——第十三天

? ? ? ? // traversal(root, list);當前做操作就行?

? ? ? ? if (root == null) {

? ? ? ? ? ? return list;

? ? ? ? }// 特殊情況的判斷

? ? ? ? while(!deq.isEmpty() || cur != null){

反序層次遍歷：

? Collections.reverse(list);//返回值是空 在原集合上進行的操作

右視圖：

平均值：

n叉樹

最大深度

最小深度：

推薦閱讀更多精彩內容

? Collections.reverse(list);//返回值是空在原集合上進行的操作