??博客主頁：?【小扳_-CSDN博客】
?感謝大家點贊??收藏?評論???
文章目錄
? ? ? ? 1.0 判斷合法
????????1.1 使用遍歷方式實現(xiàn)驗證二叉搜索樹
????????1.2 使用遞歸方式實現(xiàn)驗證二叉搜索樹
? ? ? ? 2.0 求范圍和
? ? ? ? 2.1 使用非遞歸實現(xiàn)二叉搜索樹的范圍和
? ? ? ? 2.2 使用遞歸方式實現(xiàn)二叉搜索樹的范圍和
? ? ? ? 3.0 根據(jù)前序遍歷結(jié)果建樹
????????3.1 使用非遞歸實現(xiàn)前序遍歷構造二叉搜索樹
? ? ? ? 3.2 使用遞歸實現(xiàn)前序遍歷構造二叉搜索樹
? ? ? ? 4.0 二叉搜索樹的最近祖先
????????4.1 使用遍歷方式實現(xiàn)二叉搜索樹的最近公共祖先
? ? ? ? 5.0 本篇二叉搜索樹實現(xiàn) LeetCode 經(jīng)典題的完整代碼
? ? ? ? 1.0 判斷合法
題目：
????????給你一個二叉樹的根節(jié)點?
root?，判斷其是否是一個有效的二叉搜索樹。有效?二叉搜索樹定義如下：
????????節(jié)點的左子樹只包含?小于?當前節(jié)點的數(shù)。
????????節(jié)點的右子樹只包含?大于?當前節(jié)點的數(shù)。
????????所有左子樹和右子樹自身必須也是二叉搜索樹。
示例 1：
輸入：root = [2,1,3] 輸出：trueOJ鏈接：98. 驗證二叉搜索樹
? ? ? ? 1.1 使用遍歷方式實現(xiàn)驗證二叉搜索樹
????????具體思路為：利用中序遍歷的效果，若每一個節(jié)點的值都比前一個節(jié)點的值大，則符合二叉搜索樹；若出現(xiàn)某一個節(jié)點或者多個節(jié)點的值比前一個節(jié)點的值大，則符合二叉搜索樹。
代碼如下：
//使用遍歷實現(xiàn)驗證二叉樹 public boolean isValidBST2(TreeNode node) { Stack<TreeNode> stack = new Stack<>(); TreeNode p = node; long prev = Long.MIN_VALUE; while (p != null || !stack.isEmpty()) { if (p != null) { stack.push(p); p = p.left; }else { TreeNode pop = stack.pop(); if(pop.val <= prev) { return false; } prev = pop.val; p = pop.right; } } return true; }? ? ? ? 需要注意的是，當前節(jié)點的值等于前一個節(jié)點的值時，同樣是不屬于二叉搜索樹。
? ? ? ? 1.2 使用遞歸方式實現(xiàn)驗證二叉搜索樹
????????具體思路為：利用遞歸遍歷該二叉樹時，先對節(jié)點的左子樹進行操作，若該左子樹返回的是 true 時，則繼續(xù)判斷當前節(jié)點的值 val ；若該左子樹返回的是 false 時，則不需要再進行下去了，返回 false 結(jié)束。若當前當前節(jié)點的值小于前一個節(jié)點的值，則返回? false ;若當前節(jié)點的值大于前一個節(jié)點時，需要將 prev = node.val 賦值完后，繼續(xù)判斷下去。直到遇到 node == null 時，返回 true 。若左子樹與當前的節(jié)點都為 true 時，接著到該節(jié)點的右子樹。最后當且僅當，左右子樹都為 true 時，說明該二叉樹是屬于二叉搜索樹。
代碼如下：
//使用遞歸實現(xiàn)驗證二叉樹 private long prev = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if(root == null) { return true; } boolean l = isValidBST(root.left); if (!l) { return false; } if(prev >= root.val) { return false; } prev = root.val; return isValidBST(root.right); }
? ? ? ? 2.0 求范圍和
題目：????????
????????給定二叉搜索樹的根結(jié)點?
root，返回值位于范圍?[low, high]?之間的所有結(jié)點的值的和。示例 1：
輸入：root = [10,5,15,3,7,null,18], low = 7, high = 15 輸出：32OJ鏈接：938. 二叉搜索樹的范圍和
? ? ? ? 2.1 使用非遞歸實現(xiàn)二叉搜索樹的范圍和
????????具體思路為：利用中序遍歷效果，對于滿足 node.val >?slow && node.val? < high 的節(jié)點 node 將該節(jié)點的 node.val 累加到 sum 中，直到遇到 node.val > high 時，則直接返回 sum 結(jié)果即可。
代碼如下：
//使用非遞歸求二叉搜索樹的范圍和 public int rangeSum2(TreeNode root,int slow,int high) { Stack<TreeNode> stack = new Stack<>(); TreeNode p = root; int sum = 0; while(p != null || !stack.isEmpty()) { if(p != null) { stack.push(p); p = p.left; }else { TreeNode pop = stack.pop(); if(pop.val > high) { break; } if(pop.val >= slow) { sum += pop.val; } p = pop.right; } } return sum; }
? ? ? ? 2.2 使用遞歸方式實現(xiàn)二叉搜索樹的范圍和
????????具體思路為：首先考慮符合 slow 與 high 范圍之內(nèi)的節(jié)點值，需要返回當前節(jié)點的值與該節(jié)點的左子樹與右子樹的符合范圍的節(jié)點值。再來考慮不符合 slow 與 high 范圍之內(nèi)的節(jié)點值時，當 node.val < slow ，則不能再往該節(jié)點的左子樹繼續(xù)遞歸下去了，需要往該節(jié)點的右子樹遞歸下去；當 node.val > slow ，則不能往該節(jié)點的右子樹繼續(xù)遞歸下去了，需要往該節(jié)點的左子樹遞歸尋找符合范圍值的節(jié)點。
代碼如下：
//使用遞歸求二叉搜索樹的范圍和 public int rangeSum(TreeNode root,int slow, int high) { if(root == null) { return 0; } if(root.val < slow) { return rangeSum(root.right,slow,high); } if(root.val > high) { return rangeSum(root.left,slow,high); } return root.val + rangeSum(root.left,slow,high) + rangeSum(root.right,slow,high); }
? ? ? ? 3.0 根據(jù)前序遍歷結(jié)果建樹
題目：
????????給定一個整數(shù)數(shù)組，它表示BST(即?二叉搜索樹?)的?先序遍歷?，構造樹并返回其根。
保證?對于給定的測試用例，總是有可能找到具有給定需求的二叉搜索樹。
二叉搜索樹?是一棵二叉樹，其中每個節(jié)點，?
Node.left?的任何后代的值?嚴格小于?Node.val?,?Node.right?的任何后代的值?嚴格大于?Node.val。二叉樹的?前序遍歷?首先顯示節(jié)點的值，然后遍歷
Node.left，最后遍歷Node.right。示例 1：
輸入：preorder = [8,5,1,7,10,12] 輸出：[8,5,10,1,7,null,12]OJ鏈接：1008. 前序遍歷構造二叉搜索樹
? ? ? ? ?3.1 使用非遞歸實現(xiàn)前序遍歷構造二叉搜索樹
? ? ? ? 具體思路為：利用數(shù)組中第一個值作為根節(jié)點的值，再遍歷數(shù)組從索引 1 開始直到該數(shù)組長度 - 1 。得到每一個數(shù)組的值來創(chuàng)建一個新的節(jié)點，再自定義 insert 方法將該節(jié)點插入二叉搜索樹中。關鍵的是：使用非遞歸方式實現(xiàn)該方法，首先定義一個 parent 變量，用來記錄 p 的父親節(jié)點，循環(huán)遍歷 p ，若 p.val > node.val 時，先記錄 parent = p，再 p = p.left ；若 p.val < node.val 時， 先記錄 parent = p，再 p = p.right?。直到 p == null 時，跳出循環(huán)，則當前的 parent 就是該二叉樹的葉子節(jié)點，在判斷 node.val 與 parent.val 的大小關系，若 node.val > parent.val，則 parent.right = node；若 node.val < parent.val，則 parent.left = node 。
代碼如下：
//根據(jù)前序遍歷的結(jié)果建樹 public TreeNode bstFromPreorder(int[] preorder) { TreeNode root = new TreeNode(preorder[0]); for(int i = 1; i < preorder.length; i++) { TreeNode p = new TreeNode(preorder[i]); insert(root,p); } return root; } //使用非遞歸的方式 public void insert(TreeNode root, TreeNode node) { TreeNode p = root; TreeNode parent = null; while(p != null) { if(p.val < node.val) { parent = p; p = p.right; }else if(p.val > node.val) { parent = p; p = p.left; } } if(parent.val > node.val) { parent.left = node; }else { parent.right = node; } }
? ? ? ? 3.2 使用遞歸實現(xiàn)前序遍歷構造二叉搜索樹
? ? ? ? 具體思路為：遞歸遍歷直到遇到 node == null 時，那么 node = new TreeNode(val) 。若 node.val >?val 時，向左子樹遞歸下去 node = node.left；若 node.val < val 時，先右子樹遞歸下去 node = node.right 。每一次遞歸完，返回的時候，需要重新鏈接當前節(jié)點的左子樹或者右子樹，再返回當前節(jié)點。
代碼如下：
//根據(jù)前序遍歷的結(jié)果建樹 public TreeNode bstFromPreorder(int[] preorder) { TreeNode root = new TreeNode(preorder[0]); for(int i = 1; i < preorder.length; i++) { TreeNode p = new TreeNode(preorder[i]); insert(root,p); } return root; } //使用遞歸的方式 public TreeNode insert(TreeNode node, int val) { if (node == null) { return new TreeNode(val); } if (node.val > val) { node.left = insert(node.left,val); }else { node.right = insert(node.right,val); } return node; }
? ? ? ? 4.0 二叉搜索樹的最近祖先
題目：
????????給定一個二叉搜索樹, 找到該樹中兩個指定節(jié)點的最近公共祖先。
百度百科中最近公共祖先的定義為：“對于有根樹 T 的兩個結(jié)點 p、q，最近公共祖先表示為一個結(jié)點 x，滿足 x 是 p、q 的祖先且 x 的深度盡可能大（一個節(jié)點也可以是它自己的祖先）?！?/strong>
例如，給定如下二叉搜索樹:? root =?[6,2,8,0,4,7,9,null,null,3,5]
示例 1:
輸入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 輸出: 6 解釋: 節(jié)點 2 和節(jié)點 8 的最近公共祖先是 6。OJ鏈接：235. 二叉搜索樹的最近公共祖先
? ? ? ? 4.1 使用遍歷方式實現(xiàn)二叉搜索樹的最近公共祖先
? ? ? ? 具體思路為：若 p 與 q 在當前節(jié)點的左右子樹，那么該節(jié)點就是該 q 與 p 的公共最近的祖先；若 p 與 q 在當前節(jié)點的同一側(cè)(都在該當前節(jié)點的左子樹或者右子樹)，則需要繼續(xù)往下遍歷，當 node.val < p.val && node.val < q.val 或者 node.val > p.val && node.val > q.val 都需要繼續(xù)遍歷，直到跳出循環(huán)后，則當前節(jié)點 node 就是該 p 與 q 的公共最近節(jié)點。
代碼如下：
//二叉搜索樹的最近祖宗 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { TreeNode a = root; while(p.val < a.val && q.val < a.val || p.val > a.val && q.val > a.val) { if(p.val < a.val) { a = a.left; }else { a = a.right; } } return a; }
? ? ? ? 5.0 本篇二叉搜索樹實現(xiàn) LeetCode 經(jīng)典題的完整代碼
import java.util.Stack; 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; } //使用遞歸實現(xiàn)驗證二叉樹 private long prev = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if(root == null) { return true; } boolean l = isValidBST(root.left); if (!l) { return false; } if(prev >= root.val) { return false; } prev = root.val; return isValidBST(root.right); } //使用遍歷實現(xiàn)驗證二叉樹 public boolean isValidBST2(TreeNode node) { Stack<TreeNode> stack = new Stack<>(); TreeNode p = node; long prev = Long.MIN_VALUE; while (p != null || !stack.isEmpty()) { if (p != null) { stack.push(p); p = p.left; }else { TreeNode pop = stack.pop(); if(pop.val <= prev) { return false; } prev = pop.val; p = pop.right; } } return true; } //使用遞歸求二叉搜索樹的范圍和 public int rangeSum(TreeNode root,int slow, int high) { if(root == null) { return 0; } if(root.val < slow) { return rangeSum(root.right,slow,high); } if(root.val > high) { return rangeSum(root.left,slow,high); } return root.val + rangeSum(root.left,slow,high) + rangeSum(root.right,slow,high); } //使用非遞歸求二叉搜索樹的范圍和 public int rangeSum2(TreeNode root,int slow,int high) { Stack<TreeNode> stack = new Stack<>(); TreeNode p = root; int sum = 0; while(p != null || !stack.isEmpty()) { if(p != null) { stack.push(p); p = p.left; }else { TreeNode pop = stack.pop(); if(pop.val > high) { break; } if(pop.val >= slow) { sum += pop.val; } p = pop.right; } } return sum; } //根據(jù)前序遍歷的結(jié)果建樹 public TreeNode bstFromPreorder(int[] preorder) { TreeNode root = new TreeNode(preorder[0]); for(int i = 1; i < preorder.length; i++) { TreeNode p = new TreeNode(preorder[i]); insert(root,p); } return root; } //使用非遞歸的方式 public void insert(TreeNode root, TreeNode node) { TreeNode p = root; TreeNode parent = null; while(p != null) { if(p.val < node.val) { parent = p; p = p.right; }else if(p.val > node.val) { parent = p; p = p.left; } } if(parent.val > node.val) { parent.left = node; }else { parent.right = node; } } //使用遞歸的方式 public TreeNode insert(TreeNode node, int val) { if (node == null) { return new TreeNode(val); } if (node.val > val) { node.left = insert(node.left,val); }else { node.right = insert(node.right,val); } return node; } //二叉搜索樹的最近祖宗 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { TreeNode a = root; while(p.val < a.val && q.val < a.val || p.val > a.val && q.val > a.val) { if(p.val < a.val) { a = a.left; }else { a = a.right; } } return a; } }????????
? ? ? ? 本篇為相關二叉搜索樹對于 LeetCode 題目的相關解法，希望對你有所幫助。文章來源：http://www.zghlxwxcb.cn/news/detail-779714.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-779714.html
到了這里，關于Java LeetCode篇-二叉搜索樹經(jīng)典解法（實現(xiàn)：二叉搜索樹的最近公共祖先、根據(jù)前序遍歷建樹等）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
