#Java #二叉樹 #雙指針

開源學習資料

Feeling and experiences：

二叉搜索樹的最小絕對差：力扣題目鏈接

給你一個二叉搜索樹的根節(jié)點 root ，返回 樹中任意兩不同節(jié)點值之間的最小差值 。

差值是一個正數(shù)，其數(shù)值等于兩值之差的絕對值。

之前遞歸搜索樹寫多了，導致首先想到的方法 是把每個節(jié)點與左右子樹值的差返回給上一級作比較。

但是該題目更好的做法是用中序遍歷：

/*** 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;*     }* }*/
class Solution {int minNode; //記錄答案int pre; //用來記錄前一個節(jié)點public int getMinimumDifference(TreeNode root) {//初始化最大值minNode = Integer.MAX_VALUE;//初始化為-1；pre = -1;dfs(root);return minNode;}public void dfs(TreeNode node){if(node == null){return;}//利用中序遍歷//先遍歷左子樹dfs(node.left);//用pre記錄前一個節(jié)點的值if(pre == -1){pre = node.val;}else{minNode = Math.min(minNode , node.val - pre);pre = node.val;}//遍歷右子樹dfs(node.right);}
}

整體思路很簡單：就是一個pre指針記錄上一個節(jié)點的值，與當前值進行相減之后，與minNode中存儲的結果作比較（minNode中肯定存放的是更小的值），這樣可以更新其結果，遍歷完得到最終的結果。

圖解如下：

用棧模擬，迭代法：

class Solution {public int getMinimumDifference(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode pre = null;int result = Integer.MAX_VALUE;if(root != null)stack.add(root);while(!stack.isEmpty()){TreeNode curr = stack.peek();if(curr != null){stack.pop();if(curr.right != null)stack.add(curr.right);stack.add(curr);stack.add(null);if(curr.left != null)stack.add(curr.left);}else{stack.pop();TreeNode temp = stack.pop();if(pre != null)result = Math.min(result, temp.val - pre.val);pre = temp;}}return result;}
}

?

?

二叉搜索樹中的眾數(shù)：力扣題目鏈接

給你一個含重復值的二叉搜索樹（BST）的根節(jié)點 root ，找出并返回 BST 中的所有 眾數(shù)（即，出現(xiàn)頻率最高的元素）。

如果樹中有不止一個眾數(shù)，可以按 任意順序 返回。

假定 BST 滿足如下定義：

• 結點左子樹中所含節(jié)點的值 小于等于 當前節(jié)點的值
• 結點右子樹中所含節(jié)點的值 大于等于 當前節(jié)點的值
• 左子樹和右子樹都是二叉搜索樹

我根據(jù)上一個題的思路寫了一個解法：

/*** 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;*     }* }*/
class Solution {//該樹是一個二叉搜索樹List<Integer> list = new ArrayList<>();int pre = -1;int preCount = 0;int maxCount = 0;public int[] findMode(TreeNode root) {dfs(root);addMore(pre,preCount);int [] res = new int[list.size()];for(int i =0;i<list.size();i++){res[i] = list.get(i);}return res;}public void dfs(TreeNode node){if(node == null){return;}dfs(node.left);if(pre == -1 || pre != node.val){addMore(pre,preCount);pre = node.val;preCount = 1;}else{preCount++;}dfs(node.right);}public void addMore(int value,int count){if(count > maxCount){maxCount = count;list.clear();if(value != -1)list.add(value);}else if(count == maxCount && value != -1){list.add(value);}}}

不過，這段代碼不能處理以下測試：

?

?更改后的代碼：

class Solution {ArrayList<Integer> resList;int maxCount;int count;TreeNode pre;public int[] findMode(TreeNode root) {resList = new ArrayList<>();maxCount = 0;count = 0;pre = null;findMode1(root);int[] res = new int[resList.size()];for (int i = 0; i < resList.size(); i++) {res[i] = resList.get(i);}return res;}public void findMode1(TreeNode root) {if (root == null) {return;}findMode1(root.left);int rootValue = root.val;// 計數(shù)if (pre == null || rootValue != pre.val) {count = 1;} else {count++;}// 更新結果以及maxCountif (count > maxCount) {resList.clear();resList.add(rootValue);maxCount = count;} else if (count == maxCount) {resList.add(rootValue);}pre = root;findMode1(root.right);}
}

?

?二叉樹的最近公共祖先：力扣題目鏈接

給定一個二叉樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。

百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個節(jié)點 p、q，最近公共祖先表示為一個節(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）。”

用后序遍歷，從后往前找！

/*** 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 || root == p || root == q) { // 遞歸結束條件return root;}// 后序遍歷TreeNode left = lowestCommonAncestor(root.left, p, q);TreeNode right = lowestCommonAncestor(root.right, p, q);if(left == null && right == null) { // 若未找到節(jié)點 p 或 qreturn null;}else if(left == null && right != null) { // 若找到一個節(jié)點return right;}else if(left != null && right == null) { // 若找到一個節(jié)點return left;}else { // 若找到兩個節(jié)點return root;}}
}

莫思身外無窮事，

且盡生前有限杯。

Fighting！

?

?

?