其他:

今日總結
往期打卡

---

654. 最大二叉樹

跳轉: 654. 最大二叉樹

學習: 代碼隨想錄公開講解

問題:

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

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

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

思路:

這道題要求構造二叉樹,使用前序遍歷先構造自身再構造子樹比較符合直覺,當然,先構造子節點再構造父節點后序遍歷也是沒有問題的,不過需要先存儲子節點再構造父節點,比較麻煩.當然,用中序遍歷也是,只需要先處理到左根,再創建節點,再綁定右子樹即可.所以說前中后序只是創建節點的位置不同.
但這題用層序遍歷就不是很合適,因為數組不是很好劃分,要存儲全部路徑的邊界狀態.
因為需要獲取兩個子節點再操作本節點,所以使用迭代法比較麻煩.

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(n)$

代碼(前序遞歸實現):

class Solution {TreeNode getTree(int[] nums,int l,int r){if(l>=r) return null;if(r-l==1) return new TreeNode(nums[l]);int index = l;int max = 0;for(int i=l;i<r;i++){if(nums[i]>max){max = nums[i];index = i;}}TreeNode root = new TreeNode(max);root.left = getTree(nums,l,index);root.right = getTree(nums,index+1,r);return root;}public TreeNode constructMaximumBinaryTree(int[] nums) {return getTree(nums,0,nums.length);}
}

---

617. 合并二叉樹

跳轉: 617. 合并二叉樹

學習: 代碼隨想錄公開講解

問題:

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

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

返回合并后的二叉樹。

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

思路:

兩棵樹一起遍歷,如果都不為null就合并,一方為null就返回另一方.
這里直接前序遍歷

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(logn)$

代碼:

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if(root1==null) return root2;if(root2==null) return root1;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. 二叉搜索樹中的搜索

跳轉: 700. 二叉搜索樹中的搜索

學習: 代碼隨想錄公開講解

問題:

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

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

思路:

這里直接利用二叉搜索樹的性質選擇遞歸方向即可

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

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

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(logn)$

代碼:

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

---

98. 驗證二叉搜索樹

跳轉: 98. 驗證二叉搜索樹

學習: 代碼隨想錄公開講解

問題:

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

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

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

思路:

右子樹中所有節點都大于當前節點,左子樹中所有節點都小于當前節點,基于此,可以使用邊界收縮法,判斷子節點是否在邊界內

當然,二叉搜索樹有一個很重要的性質,那就是中序遍歷下單調遞增.所以如果能想到這條性質可以降低編碼復雜度,并提升代碼效率.

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(n)$

代碼(中序遍歷):

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

代碼(邊界收縮):

class Solution {boolean handle(TreeNode root,long lBorder,long rBorder){if (root == null)return true;boolean a, b;a = true;b = true;if (root.left != null)if (root.left.val>lBorder&&root.left.val<root.val)a = handle(root.left,lBorder,root.val);elsereturn false;if (root.right != null)if (root.right.val>root.val&&root.right.val<rBorder)b = handle(root.right,root.val,rBorder);elsereturn false;return a&b;}public boolean isValidBST(TreeNode root) {return handle(root,Long.MIN_VALUE,Long.MAX_VALUE);}
}

---

2843. 統計對稱整數的數目

跳轉: 2843. 統計對稱整數的數目

問題

給你兩個正整數 low 和 high 。

對于一個由 2 * n 位數字組成的整數 x ，如果其前 n 位數字之和與后 n 位數字之和相等，則認為這個數字是一個對稱整數。

返回在 [low, high] 范圍內的 對稱整數的數目 。

思路:

找特殊數,最簡單的方法就是把所有可能用到的特殊數都記下來,然后枚舉特殊數進行判斷.當然范圍較小的情況下遍歷范圍里的數其實也差不多
當然,也可以直接枚舉每位判斷

復雜度:

• 時間復雜度: $O(n)$
• 空間復雜度: $O(n)$

代碼(哈希字典1):

class Solution {public int countSymmetricIntegers(int low, int high) {int[] hash = new int[1000];int l = 0;for(int i=1;i<10;i++){hash[l++] = i+10*i; }for(int i=1;i<10;i++){for(int j=0;j<10;j++){for(int k=0;k<10&&k<=i+j;k++){if(i+j-k>=10) continue;hash[l++]=(i*1000+j*100+k*10+(i+j-k));}}}int ans = 0;for(int i:hash){if(i<low) continue;if(i>high||i==0) break;ans++;}return ans;}
}

代碼(哈希字典2):

class Solution {public int countSymmetricIntegers(int low, int high) {int[] hash = new int[10001];for(int i=1;i<10;i++){hash[i+10*i]++; }for(int i=1;i<10;i++){for(int j=0;j<10;j++){for(int k=0;k<10&&k<=i+j;k++){if(i+j-k>=10) continue;hash[(i*1000+j*100+k*10+(i+j-k))]++;}}}int ans = 0;for(int i = low;i<=high;i++){if(hash[i]==1) ans++;}return ans;}
}

---

總結

今天主要是復習了二叉搜索樹相關的概念.

往期打卡

代碼隨想錄算法訓練營第十四天

代碼隨想錄算法訓練營第十三天

代碼隨想錄算法訓練營第十二天

代碼隨想錄算法訓練營第十一天

代碼隨想錄算法訓練營周末二

代碼隨想錄算法訓練營第十天

代碼隨想錄算法訓練營第九天

代碼隨想錄算法訓練營第八天

代碼隨想錄算法訓練營第七天

代碼隨想錄算法訓練營第六天

代碼隨想錄算法訓練營第五天

代碼隨想錄算法訓練營周末一

代碼隨想錄算法訓練營第四天

代碼隨想錄算法訓練營第三天

代碼隨想錄算法訓練營第二天

代碼隨想錄算法訓練營第一天