目錄

LeetCode.654 最大二叉樹

題目鏈接?最大二叉樹

題解

解題思路

LeetCode.617 合并二叉樹

題目鏈接??合并二叉樹

題解

解題思路

LeetCode.700 二叉搜索樹中的搜索

題目鏈接?二叉搜索樹中的搜索

題解

解題思路

解題思路

LeetCode.98 驗證二叉搜索樹

題目鏈接?驗證二叉搜索樹

題解

解題思路

解題思路

總結與收獲

---

LeetCode.654 最大二叉樹

題目鏈接?最大二叉樹

題解

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return getRoot(nums,0,nums.length);}public TreeNode getRoot(int[] nums,int begin,int end){// 獲得最大值int max_value = nums[begin];int index = begin;for(int i = index;i < end;i ++){if(max_value < nums[i]){index = i;max_value = nums[i];}}TreeNode root = new TreeNode(max_value);if(index > begin){root.left = getRoot(nums,begin,index);}if(index < end - 1){root.right = getRoot(nums,index + 1,end);}return root;}
}

解題思路

這段代碼實現了構造最大二叉樹（Maximum Binary Tree）的功能，核心思路是遞歸分治：每次從當前數組片段中找到最大值作為根節點，再遞歸處理左右子數組構建左右子樹。具體步驟如下：

1. 主函數入口：constructMaximumBinaryTree?初始化遞歸，傳入整個數組范圍?[0, nums.length)。

2. 遞歸構建樹：輔助函數?getRoot?負責：

   • 尋找最大值：遍歷當前范圍?[begin, end)，找到最大值及其索引。
   • 創建根節點：用最大值創建當前子樹的根。
   • 遞歸處理左右子樹：
     • 左子樹：處理范圍?[begin, index)（即最大值左側元素）。
     • 右子樹：處理范圍?[index+1, end)（即最大值右側元素）。
   • 返回當前根節點：將左右子樹連接到根節點后返回。

3. 遞歸終止條件：當?begin >= end?時（即處理空數組片段），返回?null。

LeetCode.617 合并二叉樹

題目鏈接??合并二叉樹

題解

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1 == null) return root2;if(root2 == null) return root1;root1.val += root2.val;root1.left = mergeTrees(root1.left,root2.left);root1.right = mergeTrees(root1.right,root2.right);return root1;}
}

解題思路

使用前序遍歷，同時對兩個樹進行遍歷。

LeetCode.700 二叉搜索樹中的搜索

題目鏈接?二叉搜索樹中的搜索

題解

class Solution {public TreeNode searchBST(TreeNode root, int val) {if(root == null) return null;if(root.val == val) return root;TreeNode resNode = null;if(val < root.val) resNode = searchBST(root.left,val);if(val > root.val) resNode = searchBST(root.right,val);return resNode;}
}

解題思路

這段代碼實現了在? 二叉搜索樹（BST） 中查找值為?val?的節點。解題思路基于 BST 的特性：左子樹所有節點值小于根節點，右子樹所有節點值大于根節點，因此可以通過比較當前節點值與目標值的大小，遞歸地縮小搜索范圍。

解題思路

1. BST 特性利用

   • 若當前節點值等于?val，直接返回當前節點。
   • 若?val?小于當前節點值，只需在左子樹中繼續搜索（因為右子樹所有值都更大）。
   • 若?val?大于當前節點值，只需在右子樹中繼續搜索（因為左子樹所有值都更小）。

2. 遞歸搜索過程

   • 終止條件：當前節點為空（未找到）或當前節點值等于?val（找到目標）。
   • 遞歸邏輯：根據當前節點值與?val?的大小關系，選擇左子樹或右子樹繼續搜索，并返回搜索結果。

3. 代碼實現步驟

   • 檢查當前節點：若為空或值匹配，直接返回。
   • 遞歸搜索：
     • 若?val < root.val，遞歸搜索左子樹。
     • 若?val > root.val，遞歸搜索右子樹。
   • 返回結果：遞歸調用的結果即為最終結果。

LeetCode.98 驗證二叉搜索樹

題目鏈接?驗證二叉搜索樹

題解

class Solution {private long prev = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root == null) return true;if(!isValidBST(root.left)) return false;if(root.val <= prev) return false;prev = root.val;return isValidBST(root.right);}
}

解題思路

這段代碼通過中序遍歷（In-order Traversal）的方式驗證二叉樹是否為合法的二叉搜索樹（BST）。解題的核心思路是利用 BST 的中序遍歷結果為嚴格升序序列這一特性，通過遞歸遍歷過程中檢查每個節點的值是否嚴格大于前一個訪問的節點值。

解題思路

1. BST 的中序遍歷特性

   • 對于合法的 BST，中序遍歷（左 → 根 → 右）的輸出必須是嚴格遞增的序列。
   • 例如，BST?[2,1,3]?的中序遍歷為?[1,2,3]，嚴格遞增。

2. 遞歸中序遍歷驗證

   • 使用全局變量?prev?記錄中序遍歷過程中前一個節點的值（初始化為?Long.MIN_VALUE）。
   • 遞歸遍歷左子樹，若左子樹不合法則直接返回?false。
   • 檢查當前節點值是否大于?prev，若不大于則返回?false。
   • 更新?prev?為當前節點值，遞歸遍歷右子樹。

3. 代碼實現步驟

   • 終止條件：空樹視為合法 BST，返回?true。
   • 遞歸左子樹：驗證左子樹是否合法。
   • 檢查當前節點：確保當前節點值大于?prev，并更新?prev。
   • 遞歸右子樹：驗證右子樹是否合法。

總結與收獲

總結上述二叉樹相關題目解法，核心均圍繞遞歸與樹的特性展開。構造最大二叉樹用遞歸分治，以最大值為根劃分左右子樹；合并二叉樹通過前序遍歷同步處理兩樹節點；BST 搜索和驗證則依托其左小右大特性，分別用遞歸縮小范圍和中序遍歷檢查升序。這些解法體現了遞歸在樹問題中的高效應用，以及利用數據結構特性簡化邏輯的關鍵思路。