【654】最大二叉樹
【617】合并二叉樹
【700】二叉搜索樹中的搜索
【98】驗證二叉搜索樹

1.【654】最大二叉樹

【654】最大二叉樹

1.1 題目描述

給定一個不重復的整數數組 nums 。 最大二叉樹 可以用下面的算法從 nums 遞歸地構建:

• 1.創建一個根節點，其值為 nums 中的最大值。
• 2.遞歸地在最大值 左邊 的 子數組前綴上 構建左子樹。
• 3.遞歸地在最大值 右邊 的 子數組后綴上 構建右子樹。

返回 nums 構建的 最大二叉樹 。

解釋： 遞歸調用如下所示：

• [3,2,1,6,0,5] 中的最大值是 6 ，左邊部分是 [3,2,1] ，右邊部分是 [0,5] 。
  • [3,2,1] 中的最大值是 3 ，左邊部分是 [] ，右邊部分是 [2,1] 。
    • 空數組，無子節點。
    • [2,1] 中的最大值是 2 ，左邊部分是 [] ，右邊部分是 [1] 。
      • 空數組，無子節點。
      • 只有一個元素，所以子節點是一個值為 1 的節點。
  • [0,5] 中的最大值是 5 ，左邊部分是 [0] ，右邊部分是 [] 。
    • 只有一個元素，所以子節點是一個值為 0 的節點。
    • 空數組，無子節點。
      
      提示：

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000
• nums 中的所有整數 互不相同

1.2 解題思路

最大二叉樹的構建過程如下：

構造樹一般采用的是前序遍歷，因為先構造根節點，然后遞歸構造左子樹和右子樹。

遞歸三部曲

• 1. 確定遞歸函數的參數和返回值

參數：存放元素的數組

返回值：返回該數組構造的二叉樹的頭結點

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

• 2. 確定終止條件

題目中說了輸入的數組大小一定是大于等于1的，所以我們不用考慮小于1的情況，那么當遞歸遍歷的時候，如果傳入的數組大小為1，說明遍歷到了葉子節點了。

那么應該定義一個新的節點，并把這個數組的數值賦給新的節點，然后返回這個節點。 這表示一個數組大小是1的時候，構造了一個新的節點，并返回。

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

• 3. 確定單層遞歸的邏輯

這里又要分為三步：

1.先要找到數組中最大的值和對應的下標， 最大的值構造根節點，下標用來下一步分割數組

		//最大值所在位置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);

2.最大值所在的下標左區間 構造左子樹
3.最大值所在的下標右區間 構造右子樹

 		//根據maxIndex劃分左右子樹root.left=travesal(nums,leftIndex,maxIndex);root.right=travesal(nums,maxIndex+1,rightIndex);

1.3 java代碼實現

class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {return travesal(nums,0,nums.length);}/*** 先找出最大元素，即根節點* 用最大元素來劃分左右子樹區間*/public TreeNode travesal(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=travesal(nums,leftIndex,maxIndex);root.right=travesal(nums,maxIndex+1,rightIndex);return root;}
}

1.4 總結

此題與【106】從中序與后序遍歷序列構造二叉樹解題思路是一樣的。此題的詳細解題思路請看【代碼隨想錄刷題】Day18 二叉樹05。

注意類似用數組構造二叉樹的題目，每次分隔盡量不要定義新的數組，而是通過下標索引直接在原數組上操作，這樣可以節約時間和空間上的開銷。

遞歸函數前面加if的情況：一般情況來說：如果讓空節點（空指針）進入遞歸，就不加if，如果不讓空節點進入遞歸，就加if限制一下， 終止條件也會相應的調整。其實這就是不同代碼風格的實現。

2.【617】合并二叉樹

【617】合并二叉樹

2.1 題目描述

給你兩棵二叉樹： root1 和 root2 。

想象一下，當你將其中一棵覆蓋到另一棵之上時，兩棵樹上的一些節點將會重疊（而另一些不會）。你需要將這兩棵樹合并成一棵新二叉樹。合并的規則是：如果兩個節點重疊，那么將這兩個節點的值相加作為合并后節點的新值；否則，不為 null 的節點將直接作為新二叉樹的節點。

返回合并后的二叉樹。

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

提示：

• 兩棵樹中的節點數目在范圍 [0, 2000] 內
• -10⁴ <= Node.val <= 10⁴

2.2 解題思路

本題使用前序遍歷。

遞歸三部曲

• 1. 確定遞歸函數的參數和返回值

首先要合入兩個二叉樹，那么參數至少是要傳入兩個二叉樹的根節點，返回值就是合并之后二叉樹的根節點。

public TreeNode mergeTrees(TreeNode root1, TreeNode root2)

• 2. 確定終止條件

因為是傳入了兩個樹，那么就有兩個樹遍歷的節點t1 和 t2，如果t1 == NULL 了，兩個樹合并就應該是 t2 了（如果t2也為NULL也無所謂，合并之后就是NULL）。

反過來如果t2 == NULL，那么兩個數合并就是t1（如果t1也為NULL也無所謂，合并之后就是NULL）。

		if(root1==null){return root2;}if (root2==null){return root1;}

• 3. 確定單層遞歸的邏輯

我們重復利用一下t1這個樹，t1就是合并之后樹的根節點（就是修改了原來樹的結構）。那么單層遞歸中，就要把兩棵樹的元素加到一起。

 root1.val+= root2.val;

接下來t1 的左子樹是：合并 t1左子樹 t2左子樹之后的左子樹。

t1 的右子樹：是 合并 t1右子樹 t2右子樹之后的右子樹。

最終t1就是合并之后的根節點。

		root1.left=mergeTrees(root1.left,root2.left);root1.right=mergeTrees(root1.right,root2.right);return root1;

2.3 java代碼實現

遞歸

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

迭代

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {//使用隊列迭代if(root1==null){return root2;}if (root2==null){return root1;}Queue<TreeNode> queue=new LinkedList<>();queue.offer(root1);queue.offer(root2);while (!queue.isEmpty()){TreeNode node1=queue.poll();TreeNode node2=queue.poll();//此時兩個節點一定不為空，值val相加node1.val+=node2.val;//如果兩棵樹左節點不為空，加入隊列if (node1.left!=null && node2.left!=null){queue.offer(node1.left);queue.offer(node2.left);}//如果兩棵樹右節點不為空，加入隊列if (node1.right!=null && node2.right!=null){queue.offer(node1.right);queue.offer(node2.right);}//若node1的左節點為空，直接賦值if (node1.left==null && node2.left!=null){node1.left=node2.left;}//若node1的右節點為空，直接賦值if (node1.right==null && node2.right!=null){node1.right=node2.right;}}return root1;}
}

3.【700】二叉搜索樹中的搜索

【700】二叉搜索樹中的搜索

3.1 題目描述

給定二叉搜索樹（BST）的根節點 root 和一個整數值 val。

你需要在 BST 中找到節點值等于 val 的節點。 返回以該節點為根的子樹。 如果節點不存在，則返回 null 。

提示：

• 樹中節點數在 [1, 5000] 范圍內
• 1 <= Node.val <= 107
• root 是二叉搜索樹
• 1 <= val <= 107

3.2 解題思路

首先要知道什么是二叉搜索樹。

二叉搜索樹是一個有序樹：

• 若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
• 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
• 它的左、右子樹也分別為二叉搜索樹

這就決定了，二叉搜索樹，遞歸遍歷和迭代遍歷和普通二叉樹都不一樣。

遞歸法

• 1. 確定遞歸函數的參數和返回值

遞歸函數的參數傳入的就是根節點和要搜索的數值，返回的就是以這個搜索數值所在的節點。

public TreeNode searchBST(TreeNode root, int val)

• 2. 確定終止條件

如果root為空，或者找到這個數值了，就返回root節點。

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

• 3. 確定單層遞歸的邏輯

看看二叉搜索樹的單層遞歸邏輯有何不同。

因為二叉搜索樹的節點是有序的，所以可以有方向的去搜索。

如果root->val > val，搜索左子樹，如果root->val < val，就搜索右子樹，最后如果都沒有搜索到，就返回NULL。

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

迭代法

一提到二叉樹遍歷的迭代法，可能立刻想起使用棧來模擬深度遍歷，使用隊列來模擬廣度遍歷。

對于二叉搜索樹可就不一樣了，因為二叉搜索樹的特殊性，也就是節點的有序性，可以不使用輔助棧或者隊列就可以寫出迭代法。

對于一般二叉樹，遞歸過程中還有回溯的過程，例如走一個左方向的分支走到頭了，那么要調頭，在走右分支。

而對于二叉搜索樹，不需要回溯的過程，因為節點的有序性就幫我們確定了搜索的方向。

例如要搜索元素為3的節點，我們不需要搜索其他節點，也不需要做回溯，查找的路徑已經規劃好了。

3.3 java代碼實現

遞歸

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

迭代

class Solution {public TreeNode searchBST(TreeNode root, int val) {//迭代while (root != null)if (val < root.val) root = root.left;else if (val > root.val) root = root.right;else return root;return null;}
}

4.【98】驗證二叉搜索樹

【98】驗證二叉搜索樹

4.1 題目描述

給你一個二叉樹的根節點 root ，判斷其是否是一個有效的二叉搜索樹。

有效 二叉搜索樹定義如下：

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

提示：

• 樹中節點數目范圍在[1, 104] 內
• -2³¹ <= Node.val <= 2³¹ - 1

4.2 解題思路

劃重點啦啦啦啦！！！！！！

要知道中序遍歷下，輸出的二叉搜索樹節點的數值是有序序列。

有了這個特性，驗證二叉搜索樹，就相當于變成了判斷一個序列是不是遞增的了。

遞歸法：
可以遞歸中序遍歷將二叉搜索樹轉變成一個數組，然后只要比較一下，這個數組是否是有序的，注意二叉搜索樹中不能有重復元素。

陷阱！！！
陷阱！！！
陷阱！！！

不能單純的比較左節點小于中間節點，右節點大于中間節點就完事了。
我們要比較的是 左子樹所有節點小于根節點，右子樹所有節點大于根節點。

比如下圖中這種情況：

節點15大于左節點10,2，小于右節點17，但是右子樹里出現了一個9這就不符合二叉搜索樹了。

遞歸三部曲:

• 1. 確定遞歸函數，返回值以及參數
     用題目中給出的即可
• 2. 確定終止條件

如果是空節點 是不是二叉搜索樹呢？是的，二叉搜索樹也可以為空！

		if (root==null){return true;}

• 3. 確定單層遞歸的邏輯

中序遍歷，一直更新max，一旦發現max >= root.val，就返回false，注意元素相同時候也要返回false。

		//左boolean left=isValidBST(root.left);if (!left){return false;}//根if (max!=null && root.val<=max.val){return false;}max=root;//右boolean right=isValidBST(root.right);return right;

迭代法：

可以用迭代法模擬二叉樹中序遍歷，那么此題將迭代法中序遍歷稍加改動就可以了。

4.3 java代碼實現

遞歸

• 先判斷左子樹，若左子樹有一個節點不是小于根節點的值，直接返回false
• 若左子樹為true，再判斷右子樹
• 若右子樹為true，整個遞歸直接返回true;若右子樹為false，整個遞歸直接返回false。

class Solution {TreeNode max;public boolean isValidBST(TreeNode root) {//遞歸if (root==null){return true;}//左boolean left=isValidBST(root.left);if (!left){return false;}//根if (max!=null && root.val<=max.val){return false;}max=root;//右boolean right=isValidBST(root.right);return right;}
}

迭代

class Solution {public boolean isValidBST(TreeNode root) {//迭代if (root==null){return true;}Stack<TreeNode> stack=new Stack<>();TreeNode pre=null;//前一個節點while (root!=null || !stack.isEmpty()){while (root!=null){stack.push(root);root=root.left;//左}//根TreeNode pop=stack.pop();if (pre!=null && pop.val<=pre.val){return false;}pre=pop;//右root=pop.right;}return true;}
}