654.最大二叉樹

力扣題目地址(opens new window)

給定一個不含重復元素的整數數組。一個以此數組構建的最大二叉樹定義如下：

• 二叉樹的根是數組中的最大元素。
• 左子樹是通過數組中最大值左邊部分構造出的最大二叉樹。
• 右子樹是通過數組中最大值右邊部分構造出的最大二叉樹。

通過給定的數組構建最大二叉樹，并且輸出這個樹的根節點。

示例 ：

提示：

給定的數組的大小在 [1, 1000] 之間。

?思路：

其實這個最大二叉樹的定義和二叉搜索樹非常像，我們能想到的是先找到里面最大的節點，將其放在根節點，然后去它的左子樹里面尋找，接著去右子樹里面尋找，屬于前序遍歷。

確定遞歸函數參數以及返回值

public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex)

我們根據傳入的數組，和數組的起始結束節點來確定邊界

確定終止條件

if (rightIndex - leftIndex < 1) {// 沒有元素了return null;}if (rightIndex - leftIndex == 1) {// 只有一個元素return new TreeNode(nums[leftIndex]);}

當沒有元素的時候直接退出，只有一個元素的時候直接return即可

確定單層遞歸的邏輯

        int maxIndex = leftIndex;// 最大值所在位置int maxVal = nums[maxIndex];// 最大值for (int i = leftIndex + 1; i < rightIndex; i++) {if (nums[i] > maxVal){maxVal = nums[i];maxIndex = i;}}TreeNode root = new TreeNode(maxVal);// 根據maxIndex劃分左右子樹root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);return root;

通過循環找到最大值，再通過遞歸左，右，最后return root即可

我們來看完整代碼、

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return constructMaximumBinaryTree1(nums, 0, nums.length);}public TreeNode constructMaximumBinaryTree1(int[] nums, int leftIndex, int rightIndex) {if (rightIndex - leftIndex < 1) {// 沒有元素了return null;}if (rightIndex - leftIndex == 1) {// 只有一個元素return new TreeNode(nums[leftIndex]);}int maxIndex = leftIndex;// 最大值所在位置int maxVal = nums[maxIndex];// 最大值for (int i = leftIndex + 1; i < rightIndex; i++) {if (nums[i] > maxVal){maxVal = nums[i];maxIndex = i;}}TreeNode root = new TreeNode(maxVal);// 根據maxIndex劃分左右子樹root.left = constructMaximumBinaryTree1(nums, leftIndex, maxIndex);root.right = constructMaximumBinaryTree1(nums, maxIndex + 1, rightIndex);return root;}
}

617.合并二叉樹

力扣題目鏈接(opens new window)

給定兩個二叉樹，想象當你將它們中的一個覆蓋到另一個上時，兩個二叉樹的一些節點便會重疊。

你需要將他們合并為一個新的二叉樹。合并的規則是如果兩個節點重疊，那么將他們的值相加作為節點合并后的新值，否則不為?NULL 的節點將直接作為新二叉樹的節點。

示例?1:

注意: 合并必須從兩個樹的根節點開始。

思路：

這道題不難，我們只需要分別對兩個數對應同一位置的節點進行比較，并且對節點進行處理就可以，采用那種遍歷方式都行

確定遞歸方法及其參數

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;

將兩個節點的值相加，然后遞歸左右節點即可

我們來看完整代碼

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;}
}

700.二叉搜索樹中的搜索

力扣題目地址(opens new window)

給定二叉搜索樹（BST）的根節點和一個值。 你需要在BST中找到節點值等于給定值的節點。 返回以該節點為根的子樹。 如果節點不存在，則返回 NULL。

例如，

在上述示例中，如果要找的值是 5，但因為沒有節點值為 5，我們應該返回 NULL。

思路：

我們找到了對應target值的節點之后進行返回操作即可，中間利用二叉搜索樹的性質進行查找

確定遞歸函數及其參數

public TreeNode searchBST(TreeNode root, int val

傳入節點和target值即可

確定終止條件

if (root == null || root.val == val) {return root;}

當根節點為空或者我們找到了對應值的節點的時候，我們直接返回就行

確定單層遞歸邏輯

if (val < root.val) {return searchBST(root.left, val);} else {return searchBST(root.right, val);}

如果root的值比target大，我們就從root的左子樹去遞歸，反之亦然

我們來看完整代碼

class Solution {// 遞歸，利用二叉搜索樹特點，優化public TreeNode searchBST(TreeNode root, int val) {if (root == null || root.val == val) {return root;}if (val < root.val) {return searchBST(root.left, val);} else {return searchBST(root.right, val);}}
}

98.驗證二叉搜索樹

力扣題目鏈接(opens new window)

給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。

假設一個二叉搜索樹具有如下特征：

• 節點的左子樹只包含小于當前節點的數。
• 節點的右子樹只包含大于當前節點的數。
• 所有左子樹和右子樹自身必須也是二叉搜索樹。

?思路 ：二叉搜索樹 左節點小于中間節點小于右節點，注意是所有左節點 下面這個情況是不符合的

不能單純的比較左節點小于中間節點，右節點大于中間節點就完事了。

寫出了類似這樣的代碼：

if (root->val > root->left->val && root->val < root->right->val) {return true;
} else {return false;
}

?確定終止條件

if (root == NULL) return true;

遞歸到空節點，我們返回true，因為空節點也是二叉搜索樹

確定單層遞歸邏輯

 boolean left = isValidBST(root.left);if (pre != null && pre.val >= root.val) return false;pre = root; // 記錄前一個節點boolean right = isValidBST(root.right);return left && right;

左中右，中序遍歷找到最左邊，最小的節點值，然后一層一層返回去判斷當前節點值是否大于pre，一旦有一個節點不滿足，就會返回false 然后向上返回回去。

我們可以通過圖示理解

    5/ \3   7/ \   \
1   4   8
isValidBST(5)
├── left = isValidBST(3)
│   ├── left = isValidBST(1)
│   │   ├── left = isValidBST(NULL) → true
│   │   ├── pre = NULL → 1
│   │   └── right = isValidBST(NULL) → true
│   │   └── 返回：true && true = true
│   ├── pre = 1 → 3
│   └── right = isValidBST(4)
│       ├── left = isValidBST(NULL) → true
│       ├── pre = 3 → 4
│       └── right = isValidBST(NULL) → true
│       └── 返回：true && true = true
│   └── 返回：true && true = true
├── pre = 4 → 5
└── right = isValidBST(7)├── left = isValidBST(NULL) → true├── pre = 5 → 7└── right = isValidBST(8)├── left = isValidBST(NULL) → true├── pre = 7 → 8└── right = isValidBST(NULL) → true└── 返回：true && true = true└── 返回：true && true = true
└── 返回：true && true = true

我們來看完整代碼

class Solution {private TreeNode pre = null; // 用來記錄前一個節點public boolean isValidBST(TreeNode root) {if (root == null) return true;boolean left = isValidBST(root.left);if (pre != null && pre.val >= root.val) return false;pre = root; // 記錄前一個節點boolean right = isValidBST(root.right);return left && right;}
}