1. 二叉樹的三種遍歷方式的實質(zhì)

這個相信大家都不會陌生, 但是大家學習這個知識點的時候, 往往并不會在意這三種遍歷的順序到底有什么意義(一般都只會打印一下值即可), 而且對這個是怎么來的也不是很清晰, 下面我們通過代碼的注釋仔細解釋一下

	public static void dfs(TreeNode node){//遞歸的終止條件(其實也就是深度優(yōu)先搜索)//即當遞歸(其實也就是搜索到空節(jié)點的時候, 就直接結束(返回),但是該函數(shù)無返回信息)if(node == null){return;}//下面是第一次來到該節(jié)點的時機(對應直接對節(jié)點進行操作,前序)System.out.println(node.val);//往左子樹搜索dfs(node.left);//下面是第二次來到該節(jié)點的時機(左子樹搜索完畢之后進行操作,中序)System.out.println(node.val);//往右子樹搜索dfs(node.right);//下面是第三次來到該節(jié)點的時機(左右子樹都搜索完畢進行操作,后序)System.out.println(node.val);}

我們現(xiàn)在創(chuàng)建一顆樹, 樹的結構是[1,2,3,4,null], 看一下上面的代碼的結果

	public static void main(String[] args) {TreeNode node1 = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);node1.left = node2;node1.right = node3;node2.left = node4;dfs(node1);}運行結果是 1 2 4 4 4 2 2 1 3 3 3 1

我們仔細研究一下上面的打印結果
把每一個數(shù)字
第一次出現(xiàn)的結果提取出來也就是
1 2 4 3(前序)
第二次出現(xiàn)的結果提取出來也就是
4 2 1 3(中序)
第三次出現(xiàn)的結果提取出來也就是
4 2 3 1(后序)
上述的結果其實正式對應二叉樹中的遞歸序
也就是幾大遍歷順序的實質(zhì)
下面我們做題的時候要時刻分析我們的遍歷順序!

2. 二叉樹的序列化與反序列化

對于一個樹狀存儲的數(shù)據(jù)來說我們需要將其序列化轉換為文本文件(字符串)便于存儲與傳輸,然后在通過反序列化的方式將其還原出來, 值得一提的是, 反序列化只能操作前序或者后序或者層序的字符串,而不能操作中序的字符串, 原因是中序的字符串是不唯一的,比如下面這一行代碼

	public static void main(String[] args) {//第一棵樹TreeNode node1 = new TreeNode(1);TreeNode node2 = new TreeNode(1);node1.left = node2;//第二棵樹node1.right = node2;}

第一顆樹的序列化結果是 " # 1 # 1 # "
第二棵樹的序列化結果也是 " # 1 # 1 # "
但是二者不是同一棵樹, 所以中序的序列化是有問題的
首先展示的我們序列化的代碼(前序舉例子)

	//創(chuàng)建一個拼接字符的static StringBuilder sp = new StringBuilder();//序列化的過程其實就是前序遍歷輸出結果的時候進行拼接即可public static String creatStringUsePreOrder(TreeNode node){//遞歸終止條件if(node == null){sp.append("#,");return sp.toString();}sp.append(node.val + ",");//遞歸的返回值其實沒有被接收(//實質(zhì)上只有最高層級的結果被調(diào)用者接收了)creatStringUsePreOrder(node.left);creatStringUsePreOrder(node.right);return sp.toString();}

序列化的過程是比較簡單的,其實就是前序遍歷加上字符串的拼接, 那如何將字符串還原為一顆二叉樹呢, 下面是我們的實現(xiàn)(已經(jīng)用split方法去除連接的","而轉化為一個String[]數(shù)組)

//定義一個下標遍歷字符串(思考為什么定義到外側)private static int index = 0;public static TreeNode creatTreeUsePreString(String[] s){//遞歸終止條件if(s[index++].equals("#")){return null;}//遞歸創(chuàng)建二叉樹//(前序遍歷的方案, 樹的連接其實是從底部連接的, 逐級返回)TreeNode root = new TreeNode(Integer.parseInt(s[index++]));root.left = creatTreeUsePreString(s);root.right = creatTreeUsePreString(s);return root;}

上述代碼我們從遞歸的角度解釋, 該函數(shù)的作用就是(創(chuàng)建一個二叉樹), 那創(chuàng)建一顆二叉樹需要創(chuàng)建出左子樹, 也需要創(chuàng)建出一顆右子樹, 所以出現(xiàn)了子問題的反復調(diào)用, 我們只需要把這個函數(shù)想象為一個"黑匣子"…

3. 根據(jù)前序中序反序列創(chuàng)建二叉樹

其實該問題就是給我們一個兩個數(shù)組(無重復數(shù)據(jù)), 一個是前序遍歷的結果, 一個是中序遍歷的結果, 然后讓我們創(chuàng)建出一顆完整的二叉樹, 我們這個問題給定的兩個數(shù)組, 可以是前序加中序, 也可以是中序加后序, 但是不可以是前序加后序(創(chuàng)建不出唯一的二叉樹), 例子自己想…, 比如下面這個例子

TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);//第一顆樹
node1.left = node2;
//第二顆樹
node1.right = node2

下面我們分析一下如何創(chuàng)建一個二叉樹(前序加上中序)
假設有一個函數(shù) func, 這個函數(shù)的功能就是創(chuàng)建二叉樹, 那么該函數(shù)的參數(shù)應該就是(傳入數(shù)據(jù)的所有信息)
> func(int[] pre,int l1,int r1,int[] in,int l2,int r2) 我們假設數(shù)組的長度都是5, 那么我們創(chuàng)建二叉樹的過程一定是從前序的結果開始的, 首先我們new出來根節(jié)點, 然后找到根節(jié)點在中序數(shù)組中所處的位置, 也就是在這個左側就是我們的左樹的部分(我們可以知道節(jié)點的規(guī)模), 右側就是右樹, 也就是說我們可以知道每一個元素在中序的位置然后控制左右邊界的位置, 最終完成二叉樹的創(chuàng)建, 由于這個過程相對抽象, 我們下面舉一個例子方便大家理解

下面是我們的代碼實現(xiàn)(用HashMap加速查詢的過程)

/*** 從前序跟中序構建一顆完整的二叉樹* 用的是一個封裝的構建函數(shù)來構建 f(pre,l1,r1,in,l1,r1)*/public TreeNode buildTree(int[] preorder, int[] inorder) {if (preorder == null || inorder == null || preorder.length != inorder.length) return null;//構建出來一張表加快構建二叉樹的過程HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < inorder.length; ++i) {map.put(inorder[i], i);}return creatTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length, map);}private TreeNode creatTree(int[] pre, int l1, int r1, int[] in, int l2, int r2, HashMap<Integer, Integer> map) {//遞歸的終止條件if (l1 > r1) {return null;}if (r1 == l1) {return new TreeNode(pre[r1]);}//借助HashMap加快查找的過程int k = map.get(pre[l1]);TreeNode node = new TreeNode(pre[l1]);node.left = creatTree(pre, l1 + 1, l1 + k - l2, in, l2, k, map);node.right = creatTree(pre, l1 + k - l2 + 1, r1, in, k + 1, r2, map);return node;}

從遞歸的角度來說, 創(chuàng)建二叉樹的這個函數(shù)相當于就是一個"黑盒", 我們要相信它可以根據(jù)我們給定的參數(shù)創(chuàng)建出一顆完整的樹, 然后我們需要去創(chuàng)建我們的左子樹, 創(chuàng)建右子樹(就出現(xiàn)了子問題復現(xiàn)的情況), 所以出現(xiàn)了遞歸

后序加上中序其實是同理的

4. 二叉樹的路徑問題

該問題涉及到回溯這一算法的概念, 其實遞歸的過程天然就帶著回溯, 那我們?yōu)槭裁匆没厮菽? 是因為在該類問題當中, 我們用一個stack收集節(jié)點的時候, 如果該節(jié)點的左右深度優(yōu)先搜索完畢之后, 我們需要把該節(jié)點彈出, 進行其他深度路徑的搜索, 其實回溯的實際也正式我們該節(jié)點的搜索任務結束的時機, 從內(nèi)存的角度來看, 也是該函數(shù)棧幀彈棧的時機

/*** 二叉樹的所有路徑* 1. 返回值是void類型 2. 遍歷的順序我們采用的是前序遍歷的順序* 3. 中途會進行節(jié)點的彈出其實也就是回溯的思路(回溯和遞歸是不分家的)*/private List<String> binaryTreePathsRes = new ArrayList<>();private ArrayDeque<Integer> stack = new ArrayDeque<>();public List<String> binaryTreePaths(TreeNode root) {binaryTreePathsFunc(root);return binaryTreePathsRes;}private void binaryTreePathsFunc(TreeNode node) {//遞歸的終止條件if (node == null) return;stack.add(node.val);//證明遞歸到了葉子節(jié)點該收獲了, 不能在null節(jié)點處收獲if (node.left == null && node.right == null) {StringBuilder sp = new StringBuilder();Iterator<Integer> it = stack.iterator();while (it.hasNext()) sp.append(it.next() + "->");sp.delete(sp.lastIndexOf("-"), sp.lastIndexOf(">") + 1);binaryTreePathsRes.add(sp.toString());stack.removeLast();}//下面就是深度優(yōu)先搜索的過程binaryTreePathsFunc(node.left);binaryTreePathsFunc(node.right);stack.removeLast();}

還有一個搜索和為targerSum的路徑然后返回, 其實是一樣的思路, 定義一個全局變量sum, 每次遍歷到的時候進行 sum += root.val , 搜索完畢之后進行回溯操作, sum -= root.val, 思路其實是一樣的

5. LCA公共祖先問題

其實就是求兩個節(jié)點p,q在一顆二叉樹的最近的公共祖先, 也是著名的LCA問題(該問題本身是很復雜的,我們先弄一個入門題), 我們知道, p,q對于一顆樹來說, 他們可能在一支上(此時q或者是p就是最近的公共祖先), 又或者是分屬于兩顆不同的樹, 此時樹的根節(jié)點就是最近的公共祖先, 我們現(xiàn)在創(chuàng)建, 其實也就是dfs對左右子樹進行深度優(yōu)先搜索的思路)

其實代碼是很簡單的

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if(root == null || root == q || root == p){return root;}//往左邊搜索TreeNode ln = lowestCommonAncestor(root.left,p,q);//往右邊搜索TreeNode rn = lowestCommonAncestor(root.right,q,p);if(ln == null && rn == null) return null;if(ln != null && rn != null) return root;return ln == null ? rn : ln;}
}

其實就是一個簡單的搜索的邏輯
總結一下本節(jié), 我們遞歸要如何想到, 我們要把這個方法當成一個黑盒子, 然后確定返回值, 終止條件等等, 另外遞歸的過程其實就是深度優(yōu)先搜索, 搜索和遞歸是不分家的, 還有搜索跟回溯是不分家的

6. 二叉搜索樹的LCA問題

常規(guī)樹的LCA解決之后, 二叉搜索樹的LCA問題其實也被包括在里面了, 但是是否有一個更好的思路來解決二叉搜索樹的最近公共祖先呢?
我們都知道, 對于二叉搜索樹來說, 左側的所側節(jié)點都小于當前節(jié)點, 右側都大于
所以我們可以把問題抽象為下面這個問題, 記作當前的節(jié)點為cur
cur == p || cur == q : cur就是我們要找到的祖先節(jié)點
cur > Math.max(p,q) : cur = cur.left (向左側移動)
cur < Math.min(p,q) : cur = cur.right (向右側移動)
Math.min(p,q) < cur < Math.max(p,q) 此時 cur就是最近公共祖先
翻譯為實現(xiàn)代碼如下

class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {return p.val > q.val ? lca(root,q,p) : lca(root,p,q);}//該方法默認的p為較小的值, q為較大的值public TreeNode lca(TreeNode root,TreeNode p,TreeNode q){while(p != root && q != root){if(root.val > p.val && root.val < q.val){return root;}root = root.val > q.val ? root.left : root.right;}return root;}
}

7. 驗證搜索二叉樹

這個問題如何想到遞歸呢, 首先二叉搜索樹的左子樹也是一個二叉搜索樹, 右子樹也是一個二叉搜索樹, 遞歸的終點其實就是葉子節(jié)點, 對于任何一個樹, 左子樹的最大值, 一定要小于中間節(jié)點的值, 右側子樹的最小值一定要大于中間節(jié)點的值, 而對于任意一個樹, 如何找到最大最小值呢, 其實就是左子樹一直向右側扎, 右子樹一直向左側扎, 代碼實現(xiàn)如下

class Solution {public boolean isValidBST(TreeNode root) {//遞歸的終止條件if(root == null) return true;if(root.left == null && root.right == null) return true;//尋找左側最大, 右側最小(設置一個前驅(qū)節(jié)點)TreeNode curl = root.left;TreeNode prel = null;TreeNode curr = root.right;TreeNode prer = null;while(curl != null){prel = curl;curl = curl.right;}while(curr != null){prer = curr;curr = curr.left;}if(prel == null){if(root.val >= prer.val) return false;}if(prer == null){if(root.val <= prel.val) return false;}if(prel != null && prer != null){if(root.val <= prel.val || root.val >= prer.val) return false;}return isValidBST(root.left) && isValidBST(root.right);}
}

遍歷方式其實就是后續(xù)遍歷, 收集到左右子樹的信息然后返回

8. 修建搜索二叉樹

這個題的意思就是上面描述的這樣, 分析的思路如下

 /*** 修剪二叉搜索樹* 問題分析 : 如果當前節(jié)點的值小于左邊界, 那么我們當前節(jié)點及其左邊都不會被保留*           如果當前節(jié)點的值大于右邊界, 那么我們當前節(jié)點及其右邊都不會被保留*           如果當前節(jié)點的值介于范圍內(nèi)部, 那么就保留當前節(jié)點遞歸修建左子樹跟右子樹** 代碼邏輯 : 我們的 "黑盒函數(shù)" 的功能是修建一顆二叉樹, 并返回修剪之后的頭節(jié)點* 實在不行自己畫遞歸圖去理解*/public TreeNode trimBST(TreeNode root, int low, int high) {//遞歸的終止條件if(root == null){return null;}if(root.val < low){return trimBST(root.right,low,high);}if(root.val > high){return trimBST(root.left,low,high);}root.left = trimBST(root.left,low,high);root.right = trimBST(root.right,low,high);return root;}

9. 二叉樹打家劫舍問題

這道題其實已經(jīng)是樹形dp了, 但是我們今天的解法大家都能聽懂, 我們用遞歸去做這道題, 我們首先定義一個全局變量yes, 和一個全局變量no, 前者代表的含義是對一個頭節(jié)點來說, 我偷了頭節(jié)點的最大收益, 后者來說是我
不偷頭節(jié)點的最大收益, 設置我們的當前節(jié)點的狀態(tài)就是n(不偷當前節(jié)點), y(偷當前節(jié)點), 所以我們的狀態(tài)轉移方程就是
y += this.no;
n += Math.max(this.yes,this.no);
我們下面的func函數(shù)執(zhí)行完畢之后就會更新全局的yes和no變量

class Solution {//yes的意思是偷頭節(jié)點的情況下, 我們能獲得的最大收益public int yes = 0;//no的意思是不偷頭節(jié)點的情況下, 我們能獲得的最大收益public int no = 0;public int rob(TreeNode root) {func(root);return Math.max(this.yes,this.no);}//該函數(shù)的功能就是給定一個頭節(jié)點, 可以得到我們此時節(jié)點的兩種最優(yōu)解的情況private void func(TreeNode root){//遞歸終止條件if(root == null){this.yes = 0;this.no = 0;}else{int y = root.val;int n = 0;func(root.left);y += this.no;n += Math.max(this.no,this.yes);func(root.right);y += this.no;n += Math.max(this.no,this.yes);this.yes = y;this.no = n;}}
}