LeetCode——樹：遞歸

---

目錄

概述

樹的高度（LeetCode104）

平衡樹（LeetCode110）

兩節(jié)點的最長路徑（LeetCode543）

翻轉(zhuǎn)樹（LeetCode226）

歸并兩棵樹（LeetCode617）

判斷路徑和是否等于一個數(shù)（LeetCode112）

統(tǒng)計路徑和等于一個數(shù)的路徑數(shù)量（LeetCode437）

子樹（LeetCode572）

樹的對稱（LeetCode101）

最小深度（LeetCode111）

統(tǒng)計左葉子節(jié)點的和（LeetCode404）

相同節(jié)點值的最大路徑長度（LeetCode687）

間隔遍歷（LeetCode337）

小結(jié)

---

0. 概述

一棵樹要么是空樹，要么有兩個指針，每個指針指向一棵樹。樹是一種遞歸結(jié)構(gòu)，很多樹的問題可以使用遞歸來處理

---

1. 樹的高度（LeetCode104）

1. 概述

2. 思路

利用遞歸，可以遍歷完全部節(jié)點（壓入棧再取出），就可以計算高度

就是假設(shè)可以獲取左節(jié)點高度：int left = maxDepth(root.left);

可以獲取右節(jié)點高度：int right = maxDepth(root.right);

返回的是root層的高度：即左右節(jié)點中高的值加1

3. 代碼

public static int maxDepth1(TreeNode root) {if (root == null) {return 0;}int left = maxDepth(root.left);int right = maxDepth(root.right);return Math.max(left, right) + 1;}

---

2. 平衡樹（LeetCode110）

1. 思路

利用遞歸，計算左右子樹最大高度差，如果超過1，則返回false。遞歸是從下面的節(jié)點往上遍歷的

2. 代碼

private static boolean result = true;public static boolean isBalanced(TreeNode root) {maxDepth(root);return result;}private static int maxDepth(TreeNode root) {if (root == null) {return 0;}int l = maxDepth(root.left);int r = maxDepth(root.right);if (Math.abs(l - r) > 1) {result = false;}return Math.max(l, r) + 1;}

---

3. 兩節(jié)點的最長路徑（LeetCode543）

1. 概述

2. 思路

利用遞歸，可以求出左右子樹的高度，加起來的結(jié)果中的最大值即為最長路徑

返回的結(jié)果是本層需要返回的結(jié)果，而不是和。

3. 代碼

private static int max = 0;public static int diameterOfBinaryTree(TreeNode root) {maxDepth(root);return max;}private static int maxDepth(TreeNode root) {if (root == null) {return 0;}int l = maxDepth(root.left);int r = maxDepth(root.right);max = Math.max(max, l + r);return Math.max(l, r) + 1;}

---

4. 翻轉(zhuǎn)樹（LeetCode226）

1. 概述

2. 思路

利用遞歸，遞歸會遍歷所有的節(jié)點，然后交換當前root的左右節(jié)點，從下一層一層往上，就會整體交換

3. 代碼

public static TreeNode invertTree(TreeNode root) {if (root == null) {return null;}TreeNode left = invertTree(root.left);TreeNode right = invertTree(root.right);root.left = right;root.right = left;return root;}

---

5. 歸并兩棵樹（LeetCode617）

1. 概述

2. 思路

對兩棵樹同時進行前序遍歷，并將對應的節(jié)點進行合并

在遍歷時，如果兩棵樹的當前節(jié)點均不為空，就將它們的值相加，并對它們的左孩子和右孩子進行遞歸合并；

如果其中有一棵樹為空，那么就返回另一棵樹作為結(jié)果。如果兩棵樹均為空，此時返回任意一棵樹均可（因為都為null）

3. 代碼

public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) {if (t1 == null && t2 == null)return null;if (t1 == null)return t2;if (t2 == null)return t1;TreeNode root = new TreeNode(t1.val + t2.val);root.left = mergeTrees(t1.left, t2.left);root.right = mergeTrees(t1.right, t2.right);return root;}

---

6. 判斷路徑和是否等于一個數(shù)（LeetCode112）

1. 概述

給定一個二叉樹和一個目標和，判斷該樹中是否存在根節(jié)點到葉子節(jié)點的路徑，這條路徑上所有節(jié)點值相加等于目標和。

2. 思路

利用遞歸，遍歷整棵樹

如果當前節(jié)點不是葉子節(jié)點，對它的所有孩子節(jié)點，遞歸調(diào)用hasPathSum函數(shù)，其中sum值減去當前節(jié)點的權(quán)值

如果當前節(jié)點為葉子節(jié)點，檢查sum值是否為0，也就是是否找到了給定的目標值

3. 代碼

public static boolean hasPathSum(TreeNode root, int sum){if (root==null){return false;}sum -= root.val;if (root.left==null&&root.right==null){return sum==0;}return hasPathSum(root.left,sum)||hasPathSum(root.right,sum);}

---

7. 統(tǒng)計路徑和等于一個數(shù)的路徑數(shù)量（LeetCode437）

1. 概述

給定一個二叉樹，它的每個結(jié)點都存放著一個整數(shù)值。找出路徑和等于給定數(shù)值的路徑總數(shù)。路徑不需要從根節(jié)點開始，也不需要在葉子節(jié)點結(jié)束，但是路徑方向必須是向下的（只能從父節(jié)點到子節(jié)點）。

2. 思路

利用遞歸可以遍歷樹的每個節(jié)點，從每個節(jié)點出發(fā)，尋找是否有等于sum的值，如果有，次數(shù)加1

總數(shù)ret=pathSumStartWithRoot(root, sum)（從root出發(fā)，是否等于sum）+ pathSum(root.left, sum)+pathSum(root.right, sum)（遍歷其他節(jié)點）

pathSumStartWithRoot(root, sum)：創(chuàng)建ret變量記錄路徑和=sum 的次數(shù)，如果root.val=sum，說明找到了要求的路徑和，ret++，否則再向它左右節(jié)點遍歷，看是否符合要求

3. 代碼

public static int pathSum(TreeNode root, int sum) {if (root == null) {return 0;}return pathSumStartWithRoot(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);}private static int pathSumStartWithRoot(TreeNode root, int sum) {if (root == null) {return 0;}int ret = 0;if (root.val == sum)ret++;ret += pathSumStartWithRoot(root.left, sum - root.val) + pathSumStartWithRoot(root.right, sum - root.val);return ret;}

---

8. 子樹（LeetCode572）

1. 概述

給定兩個非空二叉樹 s 和 t，檢驗 s 中是否包含和 t 具有相同結(jié)構(gòu)和節(jié)點值的子樹。s 的一個子樹包括 s 的一個節(jié)點和這個節(jié)點的所有子孫。s 也可以看做它自身的一棵子樹。

2. 思路

利用遞歸，return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);

isSubtreeWithRoot(s, t)：用于判斷兩個子樹是否相等
1. 如果tnull&&snull，return true
2. 如果tnull||snull，return false
3. 如果t.val!=s.val，return false
4. 再比較它們的左右節(jié)點是否相同

如果t不是當前節(jié)點s的子樹，則跳到s的左孩子或者右孩子繼續(xù)比較

3. 代碼

public static boolean isSubtree(TreeNode s, TreeNode t) {if (s == null && t == null) {return true;}if (s == null) {return false;}return isSubtreeWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);}private static boolean isSubtreeWithRoot(TreeNode s, TreeNode t) {if (s == null && t == null) {return true;}if (s == null || t == null) {return false;}if (t.val != s.val) {return false;}return isSubtreeWithRoot(s.left, t.left) && isSubtreeWithRoot(s.right, t.right);}

---

9. 樹的對稱（LeetCode101）

1. 概述

給定一個二叉樹，檢查它是否是鏡像對稱的。

2. 思路

利用遞歸，首先判斷兩個節(jié)點是否相同，不相同返回false，然后對子節(jié)點進行遞歸。s的左孩子對應t的右孩子，s的右孩子對應t的左孩子

3. 代碼

public static boolean isSymmetric(TreeNode root) {if (root == null) {return true;}return isSymmetric(root.left, root.right);}public static boolean isSymmetric(TreeNode t1, TreeNode t2) {if (t1 == null && t2 == null)return true;if (t1 == null || t2 == null)return false;if (t1.val != t2.val)return false;return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);}

---

10. 最小深度（LeetCode111）

1. 概述

給定一個二叉樹，找出其最小深度。最小深度是從根節(jié)點到最近葉子節(jié)點的最短路徑上的節(jié)點數(shù)量。

2. 思路

1. 利用遞歸，假設(shè)可以得到root的左右孩子的高度，那么最小深度就是左右孩子高度較小的那個加上自身高度，即return Math.min(left, right)+12. 而root的左右孩子也能看出一顆完整的樹，有自己左右孩子高度，依次遞歸3. 當左右孩子為null時，高度就是自己。當左右孩子有一個為null時，高度就是不為null的高度加上自己。即if(left==0||right==0) return left+right+1

3. 代碼

public static int minDepth(TreeNode root) {if (root == null) {return 0;}int left = minDepth(root.left);int right = minDepth(root.right);if (left == 0 || right == 0) {return left + right + 1;}return Math.min(left, right) + 1;}

---

11. 統(tǒng)計左葉子節(jié)點的和（LeetCode404）

1. 概述

計算給定二叉樹的所有左葉子之和。

2. 思路

利用遞歸，每一個非葉節(jié)點都可以構(gòu)成一棵樹，假設(shè)當前節(jié)點為root，判斷是否有左孩子，如果有，值相加，繼續(xù)跳到root.right遍歷。

如果當前root節(jié)點左孩子不是葉子節(jié)點，就跳到它的左孩子和右孩子繼續(xù)遍歷

也就是說利用遞歸遍歷全部節(jié)點，當遇到左葉子節(jié)點就停下來相加，否則繼續(xù)遍歷

3. 代碼

public static int sumOfLeftLeaves(TreeNode root) {if (root == null) {return 0;}if (isLeaf(root.left))return root.left.val + sumOfLeftLeaves(root.right);return sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);}private static boolean isLeaf(TreeNode node) {if (node == null)return false;return node.left == null && node.right == null;}

---

12. 相同節(jié)點值的最大路徑長度（LeetCode687）

1. 概述

給定一個二叉樹，找到最長的路徑，這個路徑中的每個節(jié)點具有相同值。 這條路徑可以經(jīng)過也可以不經(jīng)過根節(jié)點。

2. 思路

利用遞歸，可以遍歷全部節(jié)點，從下到上。

int left = dfs(root.left)，假設(shè)能獲取到左節(jié)點的最長同值長度
int right = dfs(root.right)，能獲取到右節(jié)點最長同值長度

再判斷和root節(jié)點是否相同，root.left!=null并且root.left.val==root.val，即相同的話左節(jié)點最長長度為當前長度加1，右節(jié)點同理。最長長度=Math.max(path, leftPath+rightPath)

最后返回左右節(jié)點較長的一邊

3. 代碼

private static int path = 0;public static int longestUnivaluePath(TreeNode root) {dfs(root);return path;}private static int dfs(TreeNode root) {if (root == null)return 0;int left = dfs(root.left);int right = dfs(root.right);int leftPath = root.left != null && root.left.val == root.val ? left + 1 : 0;int rightPath = root.right != null && root.right.val == root.val ? right + 1 : 0;path = Math.max(path, leftPath + rightPath);return Math.max(leftPath, rightPath);}

---

13. 間隔遍歷（LeetCode337）

1. 概述

小偷發(fā)現(xiàn)了一個新的可行竊的地區(qū)。這個地區(qū)只有一個入口，我們稱之為“根”。 除了“根”之外，每棟房子有且只有一個“父“房子與之相連。一番偵察之后，聰明的小偷意識到“這個地方的所有房屋的排列類似于一棵二叉樹”。 如果兩個直接相連的房子在同一天晚上被打劫，房屋將自動報警。

計算在不觸動警報的情況下，小偷一晚能夠盜取的最高金額。

2. 思路

root為根節(jié)點時，搶劫的金額有兩種可能
1. 如果算上root本身的值root.val，如果左子樹不為null，則再加上左子樹左右節(jié)點的值，右子樹同理。
2. 如果不算上root本身的值，則是rob(root.left)+rob(root.right)的值
3. rob函數(shù)表示以當前節(jié)點為根，能搶到最大的值

3. 代碼

public static int rob(TreeNode root){if (root==null)return 0;int val1 = root.val;if (root.left!=null)val1+=rob(root.left.left)+rob(root.left.right);if (root.right!=null)val1+= rob(root.right.left)+rob(root.right.right);int val2 = rob(root.left)+rob(root.right);return Math.max(val1,val2);}

---

14. 小結(jié)

首先，要清楚，遞歸可以遍歷所有樹的節(jié)點，比如:
int left = minDepth(root.left);
int right = minDepth(root.right);

所有，我們要關(guān)心的就是怎么對結(jié)果加工，比如求最小深度，那節(jié)點為null返回什么，一個為null返回什么，兩個為null返回什么

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的LeetCode——树：递归的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。