語言：Java/C++?

654.最大二叉樹

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

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

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

示例 ：

題目中說了輸入的數組大小一定是大于等于1的，所以我們不用考慮小于1的情況，那么當遞歸遍歷的時候，如果傳入的數組大小為1，說明遍歷到了葉子節點了。那么應該定義一個新的節點，并把這個數組的數值賦給新的節點，然后返回這個節點。

隨后找當前整個數組的最大值，根據最大值的下標將數組分為左子樹和右子樹，繼續遞歸進行構建。

class Solution {TreeNode traversal(int[] nums, int left, int right){if(right <= left ) return null;  //判空if(right-left==1){ //判斷是否為一個節點，左閉右開return new TreeNode(nums[left]);}int maxIdx=left;int maxValue=nums[left];for(int i=left+1;i<right;i++){if(nums[i]>maxValue){maxValue=nums[i];maxIdx=i;}}TreeNode node = new TreeNode(maxValue);node.left=traversal(nums, left, maxIdx);node.right=traversal(nums, maxIdx+1, right);return node;}public TreeNode constructMaximumBinaryTree(int[] nums) {return traversal(nums, 0, nums.length);}   
}

617.合并二叉樹?617.合并二叉樹?

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

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

這道題我的第一個想法是建立一個哈希表，層次遍歷并存儲第一個樹的位置和值，如果該位置沒有節點則為-1，隨后創建新的節點，遍歷第二個樹，若當前位置已經有節點，則將兩個節點值相加返回；如果第二棵樹沒有節點，但第一棵樹有，則直接返回第一棵樹的值；如果第一棵樹沒有節點，則直接返回第二棵樹的值；若第二棵樹的節點數少于第一棵樹，則在遍歷完第二棵樹后直接將第一棵樹的剩余節點返回。但是這個思路無疑增加了很多復雜性，其實遍歷兩棵樹和遍歷一棵樹的思路是一樣的，采用前序遍歷即可。

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

700.二叉搜索樹中的搜索

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

例如，

因為本文的題設是二叉搜索樹，所以這題就相對好辦了，二叉搜索樹是有序樹：

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

因此，找到值等于val的點然后遞歸返回從這個點以后的樹即可：

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

98.驗證二叉搜索樹

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

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

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

考研時數據結構里有一個結論：中序遍歷下，輸出的二叉搜索樹節點的數值是有序序列，因此可以先將樹轉換為列表或數組，再判斷是否有序即可。注意在Java中，如果將樹轉換為列表List，則需要用.get和size()來獲取列表的值和長度，如果是數組，因為不知道樹的節點個數，所以需要先設置一個很大的值，所以也可以先將樹轉換為列表，再將列表轉換為數組。

class Solution {public void traversal(TreeNode root, List<Integer> vec){if(root==null) return;traversal(root.left, vec);vec.add(root.val);traversal(root.right, vec);}public boolean isValidBST(TreeNode root) {List<Integer> res=new ArrayList<Integer>();traversal(root, res); // 將列表轉換為數組Integer[] arr=res.toArray(new Integer[res.size()]);  for(int i=1; i<arr.length;i++){if(arr[i]<=arr[i-1]) {return false; }}return true;}
}