- 二叉樹的構造默認如下：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
654. 最大二叉樹
給定一個不重復的整數陣列 nums ， 最大二叉樹 可以用下面的演算法從 nums 遞回地構建:
創建一個根節點，其值為 nums 中的最大值，
遞回地在最大值 左邊 的 子陣列前綴上 構建左子樹，
遞回地在最大值 右邊 的 子陣列后綴上 構建右子樹，
回傳 nums 構建的 最大二叉樹 ，
class Solution {
public TreeNode constructMaximumBinaryTree(int[] nums) {
TreeNode node = construct(nums, 0, nums.length);//本題陣列區間為左閉右開
return node;
}
TreeNode construct(int[] nums,int begin,int end){
if(nums.length==1){
return new TreeNode(nums[0]);//陣列的長度為1，回傳陣列中的數構建的結點
}
//遍歷陣列，得到最大值的下標
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int max = 0;
for (int i = begin; i < end; i++) {
map.put(nums[i], i);//陣列中的值為key，下標為value
max = Math.max(max,nums[i]);//找到陣列中的最大值
}
int index = map.get(max);//陣列中最大值的下標
TreeNode node = new TreeNode(max);//構建結點
if(index>begin){//如果左區間>=1
node.left = construct(nums,begin,index);
}
if(index<end-1){//如果右區間>=1
node.right = construct(nums,index+1,end);
}
return node;
}
}
- 還是構造二叉樹的題目，但是比著昨天的兩道要簡單太多了，感覺自己也慢慢理解二叉樹的遞回構造
617. 合并二叉樹
給你兩棵二叉樹： root1 和 root2 ，
想象一下，當你將其中一棵覆寫到另一棵之上時，兩棵樹上的一些節點將會重疊（而另一些不會），你需要將這兩棵樹合并成一棵新二叉樹，合并的規則是：如果兩個節點重疊，那么將這兩個節點的值相加作為合并后節點的新值；否則，不為 null 的節點將直接作為新二叉樹的節點，
回傳合并后的二叉樹，
注意: 合并程序必須從兩個樹的根節點開始，
ψ(｀?′)ψ 我的思路
- 前序遍歷兩棵樹的所有結點（思路題目上寫的很清楚了）
class Solution {
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
TreeNode node;
if (root1 == null && root2 == null) {
return null;
} else if (root1 == null && root2 != null) {
node = root2;
} else if (root2 == null && root1 != null) {
node = root1;
} else {
node = new TreeNode(root1.val+ root2.val);
node.left = mergeTrees(root1.left,root2.left);
node.right = mergeTrees(root1.right,root2.right);
}
return node;
}
}
- 麻麻，我會遞回喇??
700. 二叉搜索樹中的搜索
給定二叉搜索樹（BST）的根節點 root 和一個整數值 val，
你需要在 BST 中找到節點值等于 val 的節點， 回傳以該節點為根的子樹， 如果節點不存在，則回傳 null ，
- 考察BST的特性：當前結點左子樹所有結點的值都小于當前結點，當前結點右子樹所有結點的值都大于當前結點
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if(root==null){
return null;
}
if(root.val==val){
return root;
}
else if(root.val>val){
return searchBST(root.left,val);}
else
return searchBST(root.right,val);
}
}
時間復雜度O(n)
- 今天的題寫的特別順欸，不知道是我進步了，還是題變簡單了
98. 驗證二叉搜索樹
給你一個二叉樹的根節點 root ，判斷其是否是一個有效的二叉搜索樹，
有效 二叉搜索樹定義如下：
節點的左子樹只包含 小于 當前節點的數，
節點的右子樹只包含 大于 當前節點的數，
所有左子樹和右子樹自身必須也是二叉搜索樹，
BST用中序遍歷，結點值遞增
class Solution {
//中序遍歷
long max = Long.MIN_VALUE;//因為題目中最小結點的最小值是從Integer.MIN_VALUE開始的，要找比這個數還小的值，所以選了Long.MIN_VALUE
public boolean isValidBST(TreeNode root) {
if(root==null){return true;}//空結點既是二叉搜索樹，又是平衡樹，又是完全二叉樹，又是滿二叉樹
boolean left = isValidBST(root.left);//左
if (root.val>max){//中
max = root.val;//把當前值賦給max
} else {
return false;//當前結點的值小于等于上一個結點的值，不是BST
}
boolean right = isValidBST(root.right);//右
return left && right;
}
}
- 代碼還可以改進成雙指標，這樣就不用想著怎么找比結點的最小值還小的數了
530. 二叉搜索樹的最小絕對差
ψ(｀?′)ψ 我的思路
- 中序遍歷得到遞增的鏈表，遍歷鏈表求兩個相鄰元素的差值，取最小
class Solution {
public int getMinimumDifference(TreeNode root) {
List<Integer> path = new ArrayList<>();
inOrder(root,path);
Integer[] nums = path.toArray(new Integer[0]);
int fast=1;
int slow =0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length-1; i++) {
min = Math.min(min,nums[fast]-nums[slow]);
fast++;
slow++;
}
return min;
}
void inOrder(TreeNode root, List<Integer> path){
if(root.left!=null){
inOrder(root.left,path);
}
path.add(root.val);
if(root.right!=null){
inOrder(root.right,path);
}
}
}
501. 二叉搜索樹中的眾數
給你一個含重復值的二叉搜索樹（BST）的根節點 root ，找出并回傳 BST 中的所有 眾數（即，出現頻率最高的元素），
如果樹中有不止一個眾數，可以按 任意順序 回傳，
假定 BST 滿足如下定義：
結點左子樹中所含節點的值 小于等于 當前節點的值
結點右子樹中所含節點的值 大于等于 當前節點的值
左子樹和右子樹都是二叉搜索樹
本題BST的定義發生改變：
結點左子樹中所含節點的值 小于等于 當前節點的值
結點右子樹中所含節點的值 大于等于 當前節點的值
- ?標記，標記，這題很好，雙指標中序遍歷BST，通過更新結果集的方式減少一次遍歷
- 下面是我聽完視頻后的第一次實作，把要用到的東西全加在了引數里，結果不行，引數一直在變，
class Solution {
TreeNode pre;
int count;
public int[] findMode(TreeNode root) {
List<Integer> res = new ArrayList<>();
int maxCount = 1;
inOrder(root,count,maxCount,res);
int[] result = new int[res.size()];
for (int i = 0; i < result.length; i++) {
result[i] = res.get(i);
}
return result;
}
// 中序遍歷
void inOrder(TreeNode cur,int count,int maxCount,List<Integer> res){
if(cur==null){return;}
if(cur.left!=null){inOrder(cur.left,count,maxCount,res);}//左
if(pre == null){
count = 1;//上一結點為空時，當前結點是第一個結點
}
else if (cur.val == pre.val){
count++;//當前結點和上一結點的值相等，count++
} else {
count = 1;//當前結點和上一結點的值不等，count=1
}
if(count==maxCount){
res.add(cur.val);//如果當前結點的次數=最大次數時，當前結點的值加入到結果集中
}
if(count>maxCount){
//如果當前結點的count>最大次數
maxCount = count;//更新maxCount
res.clear();//清空res
res.add(cur.val);
}
pre = cur;
if(cur.right!=null){inOrder(cur.right,count,maxCount,res);}//右
}
}
- 把引數拿出來，測驗通過
class Solution {
int count;
List<Integer> res = new ArrayList<>();
TreeNode pre;
int maxCount;
public int[] findMode(TreeNode root) {
inOrder(root);
int[] result = new int[res.size()];
for (int i = 0; i < result.length; i++) {
result[i] = res.get(i);
}
return result;
}
// 中序遍歷
void inOrder(TreeNode cur){
if(cur==null){return;}
if(cur.left!=null){inOrder(cur.left);}//左
if(pre == null){
count = 1;//上一結點為空時，當前結點是第一個結點
}
else if (cur.val == pre.val){
count++;//當前結點和上一結點的值相等，count++
} else {
count = 1;
}
if(count==maxCount){
res.add(cur.val);//如果當前結點的次數=最大次數時，當前結點的值加入到結果集中
}
if(count>maxCount){
//如果當前結點的count>最大次數
maxCount = count;//更新maxCount
res.clear();//清空res
res.add(cur.val);
}
pre = cur;
if(cur.right!=null){inOrder(cur.right);}//右
}
}
- 挺難的這題，卡我一天
236. 二叉樹的最近公共祖先
給定一個二叉樹, 找到該樹中兩個指定節點的最近公共祖先，
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節點 p、q，最近公共祖先表示為一個節點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先），”
所有 Node.val 互不相同 ，
p != q
p 和 q 均存在于給定的二叉樹中，
-
要找最近的公共祖先，就要從下往上遍歷，選擇后序遍歷，找到目標（p,q）就向上回傳，如果當前結點的左右孩子都不空，就是結果，把結果再向上傳遞，
-
有一種特例就是，一個目標結點a在另一個目標結點p里面，此時結果為p，這時我們只會找到一個目標結點p，當遇到結點p時就回傳p，并不會再遍歷到a，因為找不到另一個結點，p會被一直向上傳遞，最侄訓傳，所以即使我們不再特殊處理這種情況，也對結果沒有影響，
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){return null;}
if(root==p||root==q){
return root;//找到目標值解回傳
}
TreeNode left = null;
if(root.left!=null){
left = lowestCommonAncestor(root.left, p, q);//左
}
TreeNode right = null;
if(root.right!=null){
right = lowestCommonAncestor(root.right, p, q);//右
}
//下面是中的邏輯
if(left!=null&&right!=null){
return root;//如果左右都有目標，回傳當前結點
} else if (left!=null&&right==null) {
return left;//如果左孩子有目標值回傳左孩子
} else if (left==null&&right!=null) {
return right;//如果右孩子有目標值回傳右孩子
} else {
return null;//左右都沒有找到目標，回傳null
}
}
}
235. 二叉搜索樹的最近公共祖先
給定一個二叉搜索樹, 找到該樹中兩個指定節點的最近公共祖先，
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結點 p、q，最近公共祖先表示為一個結點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節點也可以是它自己的祖先），”
- 用上題的方法完全可解，但是BST有它自己的特性（如果當前結點的值在p，q之間，當前結點即為所求）
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){return null;}
if(root.val>p.val&&root.val>q.val){//如果當前結點的值大于p,q的值，就在當前左子樹中尋找
root = lowestCommonAncestor(root.left, p, q);
} else if(root.val<p.val&&root.val<q.val){//如果當前結點的值小于p,q的值，就在當前右子樹中尋找
root = lowestCommonAncestor(root.right,p,q);
} else if (root.val>p.val&&root.val<q.val) {//如果當前的結點值在p和q之間，當前結點即為所求
return root;
}
return root;
}
}
701. 二叉搜索樹中的插入操作
給定二叉搜索樹（BST）的根節點 root 和要插入樹中的值 value ，將值插入二叉搜索樹， 回傳插入后二叉搜索樹的根節點， 輸入資料 保證 ，新值和原始二叉搜索樹中的任意節點值都不同，
注意，可能存在多種有效的插入方式，只要樹在插入后仍保持為二叉搜索樹即可， 你可以回傳 任意有效的結果 ，
- 思路還是比較清晰的，插入的值小于當前結點的時候，左子樹空直接插，左子樹不空呼叫遞回插入左子樹中，右邊一樣
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root==null){return new TreeNode(val);}
if(val< root.val){
//要插入的值小于當前結點的值
if(root.left==null){root.left = new TreeNode(val);}//結點的左子樹為空，直接插入
else {root.left = insertIntoBST(root.left,val);}//左子樹不空，就在左子樹里插入
}
else if (val> root.val) {
//要插入的值大于當前結點的值
if(root.right==null){root.right = new TreeNode(val);}//結點的右子樹為空，直接插入
else {root.right = insertIntoBST(root.right,val);}//就在右子樹里插入
}
return root;
}
}
450. 洗掉二叉搜索樹中的節點
給定一個二叉搜索樹的根節點 root 和一個值 key，洗掉二叉搜索樹中的 key 對應的節點，并保證二叉搜索樹的性質不變，回傳二叉搜索樹（有可能被更新）的根節點的參考，
分以下5種情況：
-
要洗掉的結點在二叉樹中不存在
-
要洗掉的結點存在于二叉樹中：
（1） 要洗掉的結點下沒有孩子，直接回傳null
（2） 要洗掉的結點下只有左孩子，回傳他的左孩子
（3） 要洗掉的結點下只有右孩子，回傳他的右孩子
（4） 要洗掉的結點下有兩個孩子，臨時變數保存這兩個孩子，右孩子繼位并找右孩子的最左側結點，把保存的左孩子掛在上面
class Solution {
TreeNode temp1;
TreeNode temp2;
public TreeNode deleteNode(TreeNode root, int key) {
if(root==null){return null;}
if(root.val==key){//找到要洗掉的結點時
if(root.left==null&&root.right==null){
return null;//如果當前結點是葉子結點
} else if (root.left!=null&&root.right==null) {
return root.left;//當前結點只有左孩子，左孩子繼位
} else if (root.left==null&&root.right!=null) {
return root.right;//當前結點只有右孩子，右孩子繼位
} else {
//當前結點有兩個孩子
temp1 = root.left;//先把root的左孩子存起來
temp2 = root.right;//把當前結點儲存起來
root = root.right;//讓右孩子繼位
while (root.left!=null){root = root.left;}//找到右子樹下最左側的結點
root.left = temp1;//把原來結點的左孩子掛在找到的結點下
return temp2;
}
}
if(key<root.val){
//去左子樹下刪
root.left = deleteNode(root.left, key);
}
if(key>root.val){
//去右子樹下刪
root.right = deleteNode(root.right, key);
}
return root;
}
}
總結
- 今天的題也很好，感覺可以慢慢理解二叉樹的遞回了，二叉樹章節還剩三道題，留到周日再寫，周日再回來補，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/514177.html
標籤：其他
上一篇：leet Code [34. Find First and Last Position of Element in Sorted Array]