Merge pull request youngyangyang04#459 from xllpiupiu/master

669修剪二叉搜索树JavaScript版本
TwStarLord · Jul 3, 2021 · b078cc2 · b078cc2
2 parents 754cb0d + 361589a
commit b078cc2
Showing 1 changed file with 53 additions and 0 deletions.
diff --git a/problems/0669.修剪二叉搜索树.md b/problems/0669.修剪二叉搜索树.md
@@ -315,6 +315,59 @@ func trimBST(root *TreeNode, low int, high int) *TreeNode {
 ```
 
 
+JavaScript版本：
+迭代：
+```js
+var trimBST = function(root, low, high) {
+   if(root === null) {
+       return null;
+   }
+   while(root !==null &&(root.val<low||root.val>high)) {
+       if(root.val<low) {
+           root = root.right;
+       }else {
+           root = root.left;
+       }
+   }
+   let cur = root;
+   while(cur!==null) {
+       while(cur.left&&cur.left.val<low) {
+           cur.left = cur.left.right;
+       }
+       cur = cur.left;
+   }
+   cur =  root;
+   //判断右子树大于high的情况
+   while(cur!==null) {
+       while(cur.right&&cur.right.val>high) {
+           cur.right = cur.right.left;
+       }
+       cur = cur.right;
+   }
+   return root;
+};
+```
+
+递归：
+```js
+var trimBST = function (root,low,high) { 
+    if(root === null) {
+        return null;
+    }
+    if(root.val<low) {
+        let right = trimBST(root.right,low,high);
+        return right;
+    }
+    if(root.val>high) {
+        let left = trimBST(root.left,low,high);
+        return left;
+    }
+    root.left = trimBST(root.left,low,high);
+    root.right = trimBST(root.right,low,high);
+    return root;
+ }
+```
+
 
 -----------------------
 * 作者微信：[程序员Carl](https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw)