144 :?前序遍歷
94 :? ?中序遍歷
145:??后序遍歷
回溯:
22 ：括號(hào)生成
78:? 子集
90:? 子集2
77:? 組合
46: 全排列（最經(jīng)典）
938: 二叉搜索樹(shù)的范圍
dfs和bfs
200: 島嶼數(shù)量(經(jīng)典)
102: 二叉樹(shù)層級(jí)遍歷 bfs
107 ：二叉樹(shù)的層序遍歷2
中等難度題目:
124:二叉樹(shù)中的最大路徑和? ? ? ? ? 難? 二叉樹(shù)
104: 二叉樹(shù)的最大深度? ? ? ? ? ? ? ? ?二叉樹(shù)
103:? ?二叉樹(shù)的鋸齒形層序遍歷? ? ?二叉樹(shù)
199:? 二叉樹(shù)的右視圖? ? ? ? ? ? ? ? ? ??二叉樹(shù)
劍指offer題目:
32:從上到下打印二叉樹(shù)
68: 二叉樹(shù)的最近公共祖仙(leetcode236)
二叉樹(shù):(二叉樹(shù)前序、中序疲恢、后序遍歷)
https://juejin.cn/post/6844903960898174984
采用遞歸和非遞歸對(duì)二叉樹(shù)進(jìn)行前序遍歷
二叉樹(shù)的后續(xù)遍歷寓调，非遞歸實(shí)現(xiàn)
概念:
? ? 算法：判斷一棵樹(shù)是否是平衡二叉樹(shù)鏡像二叉樹(shù)阿趁；
什么是完全二叉樹(shù)？
算法熟悉么桅咆？給了一個(gè)二叉排序樹(shù)，出了一個(gè)給定節(jié)點(diǎn)找到它的下一個(gè)元素（指的是大小順序的下一個(gè)）的算法題
最值:
距離
計(jì)算二叉樹(shù)的最大深度，要求非遞歸算法绿店。
任意一顆二叉樹(shù)，求最大節(jié)點(diǎn)距離
任意二叉樹(shù)，求出其中最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)間的距離
路徑
二叉樹(shù)的最低深度路徑打印
8.二叉樹(shù)給出根節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)假勿，找出從根節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑
算法題：二叉樹(shù)中和為某一值的路徑
節(jié)點(diǎn):
二叉樹(shù)某一層有多少個(gè)節(jié)點(diǎn)
8.算法題：二叉樹(shù)的每一層最左邊節(jié)點(diǎn)算法題: 230. 二叉搜索樹(shù)中第K小的元素 - 力扣（LeetCode） (leetcode-cn.com)
如果你想學(xué)好算法借嗽，建議上面二叉樹(shù)的題目都刷一下。如果你只是想應(yīng)付面試转培，主要看一下高頻的面試題目即可恶导。
最重要:? ? 二叉樹(shù)的前序遍歷，中序遍歷浸须，后續(xù)遍歷惨寿，記住，遞歸和非遞歸解法都要會(huì)删窒。學(xué)會(huì)舉一反三裂垦。
DFS和bfs,回溯算法和遞歸算法的常規(guī)題目考察
常見(jiàn)的 BST 算法。二叉查找樹(shù)的最近公共祖先（兩個(gè)元素的肌索，三個(gè)元素的蕉拢，多個(gè)元素呢）。二叉樹(shù)的最近公共祖先诚亚。
? ? 最值問(wèn)題包含(路徑,距離,節(jié)點(diǎn),k值問(wèn)題)
樹(shù)的遞歸晕换。比如樹(shù)的深度，最小深度站宗，樹(shù)的鏡像闸准。
二叉樹(shù)種類(lèi)
滿二叉樹(shù)
對(duì)于一棵二叉樹(shù)，如果每一個(gè)非葉子節(jié)點(diǎn)都存在左右子樹(shù)梢灭，并且二叉樹(shù)中所有的葉子節(jié)點(diǎn)都在同一層中夷家，這樣的二叉樹(shù)稱(chēng)為滿二叉樹(shù)。
完全二叉樹(shù)
對(duì)于一棵具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)按照層次編號(hào)敏释，同時(shí)瘾英，左右子樹(shù)按照先左后右編號(hào)，如果編號(hào)為i的節(jié)點(diǎn)與同樣深度的滿二叉樹(shù)中編號(hào)為i的節(jié)點(diǎn)在二叉樹(shù)中的位置完全相同颂暇，則這棵二叉樹(shù)稱(chēng)為完全二叉樹(shù)缺谴。
平衡二叉樹(shù)：
又稱(chēng) AVL 樹(shù)。平衡二叉樹(shù)是二叉搜索樹(shù)的進(jìn)化版耳鸯，所謂平衡二叉樹(shù)指的是湿蛔，左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1。
二叉排序樹(shù)：
又稱(chēng)二叉查找樹(shù)（Binary Search Tree）县爬，亦稱(chēng)二叉搜索樹(shù)阳啥。二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：
若左子樹(shù)不空财喳，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值察迟；
若右子樹(shù)不空斩狱，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；
左扎瓶、右子樹(shù)也分別為二叉排序樹(shù)所踊；
沒(méi)有鍵值相等的節(jié)點(diǎn)
二分查找的時(shí)間復(fù)雜度是O(log(n))，最壞情況下的時(shí)間復(fù)雜度是O(n)（相當(dāng)于順序查找）
紅黑樹(shù)：
紅黑樹(shù)是每個(gè)節(jié)點(diǎn)都帶顏色的樹(shù)概荷，節(jié)點(diǎn)顏色或是紅色或是黑色秕岛，紅黑樹(shù)是一種查找樹(shù)。紅黑樹(shù)有一個(gè)重要的性質(zhì)误证，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長(zhǎng)的路徑不多于最短的路徑的長(zhǎng)度的兩倍继薛。對(duì)于紅黑樹(shù)，插入愈捅，刪除遏考，查找的復(fù)雜度都是O（log N）。
1.數(shù)的基本概念題目(高度,深度,平衡,滿二叉樹(shù))
?樹(shù)的高度
1.0 求二叉樹(shù)的最大層數(shù)(最大深度)
104. Maximum Depth of Binary Tree (Easy)
平衡樹(shù)
110. Balanced Binary Tree (Easy)
2. 前中后序遍歷(遞歸實(shí)現(xiàn)和非遞歸實(shí)現(xiàn))
遍歷方式
二叉樹(shù)主要有四種遍歷方式
先序(先根)遍歷：即先訪問(wèn)根節(jié)點(diǎn)蓝谨，再訪問(wèn)左孩子和右孩子
中序遍歷：先訪問(wèn)做孩子灌具，再訪問(wèn)根節(jié)點(diǎn)和右孩子
后序遍歷：先訪問(wèn)左孩子，再訪問(wèn)右孩子像棘，再訪問(wèn)根節(jié)點(diǎn)
層次遍歷：按照所在層數(shù)稽亏，從下往上遍歷
遞歸
一棵樹(shù)要么是空樹(shù)壶冒，要么有兩個(gè)指針缕题，每個(gè)指針指向一棵樹(shù)。樹(shù)是一種遞歸結(jié)構(gòu)胖腾，很多樹(shù)的問(wèn)題可以使用遞歸來(lái)處理烟零。
前:leetcode144
中:leetcode94
后:leetcode145
二叉樹(shù)的鋸齒形層序遍歷?
非遞歸實(shí)現(xiàn)二叉樹(shù)的前序遍歷
145. Binary Tree Postorder Traversal (Medium)
前序遍歷為 root -> left -> right，后序遍歷為 left -> right -> root咸作∠前ⅲ可以修改前序遍歷成為 root -> right -> left，那么這個(gè)順序就和后序遍歷正好相反记罚。
publicListpostorderTraversal(TreeNode root){? ? List ret =newArrayList<>();? ? Stack stack =newStack<>();? ? stack.push(root);while(!stack.isEmpty()) {TreeNodenode=stack.pop();if(node ==null)continue;? ? ? ? ret.add(node.val);? ? ? ? stack.push(node.left);? ? ? ? stack.push(node.right);? ? }? ? Collections.reverse(ret);returnret;}復(fù)制代碼
非遞歸實(shí)現(xiàn)二叉樹(shù)的中序遍歷
94. Binary Tree Inorder Traversal (Medium)
publicListinorderTraversal(TreeNode root){? ? List ret =newArrayList<>();if(root ==null)returnret;? ? Stack stack =newStack<>();TreeNodecur=root;while(cur !=null|| !stack.isEmpty()) {while(cur !=null) {? ? ? ? ? ? stack.push(cur);? ? ? ? ? ? cur = cur.left;? ? ? ? }TreeNodenode=stack.pop();? ? ? ? ret.add(node.val);? ? ? ? cur = node.right;? ? }returnret;}
leetcode 32:從上到下打印二叉樹(shù)
BST(二叉查找樹(shù))
二叉查找樹(shù)（BST）：根節(jié)點(diǎn)大于等于左子樹(shù)所有節(jié)點(diǎn)墅诡，小于等于右子樹(shù)所有節(jié)點(diǎn)。
二叉查找樹(shù)中序遍歷有序桐智。
二叉樹(shù)的最近公共祖先:leetcode236
最值:
距離
計(jì)算二叉樹(shù)的最大深度末早，要求非遞歸算法。
任意一顆二叉樹(shù)说庭，求最大節(jié)點(diǎn)距離
任意二叉樹(shù)然磷，求出其中最遠(yuǎn)的兩個(gè)節(jié)點(diǎn)間的距離
路徑
二叉樹(shù)的最低深度路徑打印
8.二叉樹(shù)給出根節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，找出從根節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑
算法題：二叉樹(shù)中和為某一值的路徑
節(jié)點(diǎn):
二叉樹(shù)某一層有多少個(gè)節(jié)點(diǎn)
8.算法題：二叉樹(shù)的每一層最左邊節(jié)點(diǎn)算法題: 230. 二叉搜索樹(shù)中第K小的元素 - 力扣（LeetCode） (leetcode-cn.com)
