递归、迭代、前序遍历，3 解法，求解《669. 修剪二叉搜索树》

代码数据结构:树数据结构:二叉树数据结构:二叉平衡树算法:递归算法:迭代语言:JavaScript 语言:Go 语言:PHP 语言:Python 语言:C 语言:C++语言:C#语言:Java 语言:TypeScript

2022-09-10 06:14:28

递归、迭代、前序遍历，3 解法，求解《669. 修剪二叉搜索树》

例题

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在唯一的答案。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
示例 1：

输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]
示例 2：

输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]
提示：
树中节点数在范围 [1, 104] 内
0 <= Node.val <= 104
树中每个节点的值都是唯一的
题目数据保证输入是一棵有效的二叉搜索树
0 <= low <= high <= 104

答案

递归

var trimBST = function(root, low, high) {
  if (root == null) return null
  if (root.val < low) return trimBST(root.right, low, high)
  if (root.val > high) return trimBST(root.left, low, high)
  root.left = trimBST(root.left, low, high)
  root.right = trimBST(root.right, low, high)
  return root
};

var trimBST = function(root, low, high) {
  return (function d(n) {
    if (n === null) return null
    if (n.val < low) return d(n.right)
    if (n.val > high) return d(n.left)
    n.left = d(n.left)
    n.right = d(n.right)
    return n
  })(new TreeNode(-1, null, root))
};

function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null {
  if (root == null) return null
  if (root.val < low) return trimBST(root.right, low, high)
  if (root.val > high) return trimBST(root.left, low, high)
  root.left = trimBST(root.left, low, high)
  root.right = trimBST(root.right, low, high)
  return root
};

class Solution {
  function trimBST($root, $low, $high) {
    if ($root === null) return null;
    if ($root->val < $low) return $this->trimBST($root->right, $low, $high);
    if ($root->val > $high) return $this->trimBST($root->left, $low, $high);
    $root->left = $this->trimBST($root->left, $low, $high);
    $root->right = $this->trimBST($root->right, $low, $high);
    return $root;
  }
}

func trimBST(root *TreeNode, low int, high int) *TreeNode {
  if root == nil {
    return nil
  }
  if root.Val < low {
    return trimBST(root.Right, low, high)
  }
  if root.Val > high {
    return trimBST(root.Left, low, high)
  }
  root.Left = trimBST(root.Left, low, high)
  root.Right = trimBST(root.Right, low, high)
  return root
}

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

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

struct TreeNode* trimBST(struct TreeNode* root, int low, int high){
  if (root == NULL) return NULL;
  if (root->val < low) return trimBST(root->right, low, high);
  if (root->val > high) return trimBST(root->left, low ,high);
  root->left = trimBST(root->left, low, high);
  root->right = trimBST(root->right, low, high);
  return root;
}

class Solution {
public:
  TreeNode* trimBST(TreeNode* root, int low, int high) {
    if (root == nullptr) return nullptr;
    if (root->val < low) return trimBST(root->right, low, high);
    if (root->val > high) return trimBST(root->left, low, high);
    root->left = trimBST(root->left, low, high);
    root->right = trimBST(root->right, low, high);
    return root;
  }
};

class Solution:
  def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
    if root == None: return None
    if root.val < low: return self.trimBST(root.right, low, high)
    elif root.val > high: return self.trimBST(root.left, low, high)
    root.left = self.trimBST(root.left, low, high)
    root.right = self.trimBST(root.right, low, high)
    return root

迭代

从根节点出发，找到符合条件的节点

该节点左子树中的右子树一定符合要求，只需修剪左子树
- 找到不符合要求的左子树节点，跳该左子树的右子树（右子树一定符合要求，不会出现连跳 2 次都不符合要求的情况）
该节点右子树中的左子树一定符合要求，只需修建右子树
- 找到不符合要求的右子树节点，跳该右子树的左子树（左子树一定符合要求，不会出现连跳 2 次都不符合要求的情况）

var trimBST = function(root, low, high) {
  while (root && (root.val < low || root.val > high)) {
    if (root.val < low) root = root.right
    else if (root.val > high) root = root.left
  }
  if (root == null) return null
  for (let n = root; n.left;) {
    if (n.left.val < low) n.left = n.left.right
    else n = n.left
  }
  for (let n = root; n.right;) {
    if (n.right.val > high) n.right = n.right.left
    else n = n.right
  }
  return root
};

function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null {
  while (root != null && (root.val < low || root.val > high)) {
    if (root.val < low) root = root.right
    else if (root.val > high) root = root.left
  }
  if (root == null) return null
  for (let n = root; n.left != null;) {
    if (n.left.val < low) n.left = n.left.right
    else n = n.left
  }
  for (let n = root; n .right != null;) {
    if (n.right.val > high) n.right = n.right.left
    else n = n.right
  }
  return root
};

class Solution {
  function trimBST($root, $low, $high) {
    while ($root != null && ($root->val < $low || $root->val > $high)) {
      if ($root->val < $low) $root = $root->right;
      if ($root->val > $high) $root = $root->left;
    }
    if ($root == null) return null;
    for ($n = $root; $n->left != null;) {
      if ($n->left->val < $low) $n->left = $n->left->right;
      else $n = $n->left;
    }
    for ($n = $root; $n->right != null;) {
      if ($n->right->val > $high) $n->right = $n->right->left;
      else $n = $n->right;
    }
    return $root;
  }
}

func trimBST(root *TreeNode, low int, high int) *TreeNode {
  for root != nil && (root.Val < low || root.Val > high) {
    if root.Val < low {
      root = root.Right
    }
    if root.Val > high {
      root = root.Left
    }
  }
  if root == nil {
    return nil
  }
  for n := root; n.Left != nil; {
    if n.Left.Val < low {
      n.Left = n.Left.Right
    } else {
      n = n.Left
    }
  }
  for n := root; n.Right != nil; {
    if n.Right.Val > high {
      n.Right = n.Right.Left
    } else {
      n = n.Right
    }
  }
  return root
}

class Solution {
  public TreeNode trimBST(TreeNode root, int low, int high) {
    while (root != null && (root.val < low || root.val > high)) {
      if (root.val < low) root = root.right;
      if (root.val > high) root = root.left;
    }
    if (root == null) return null;
    for (TreeNode n = root; n.left != null;) {
      if (n.left.val < low) n.left = n.left.right;
      else n = n.left;
    }
    for (TreeNode n = root; n.right != null;) {
      if (n.right.val > high) n.right = n.right.left;
      else n = n.right;
    }
    return root;
  }
}

public class Solution {
  public TreeNode TrimBST(TreeNode root, int low, int high) {
    while (root != null && (root.val < low || root.val > high)) {
      if (root.val < low) root = root.right;
      else if (root.val > high) root = root.left;
    }
    if (root == null) return null;
    for (TreeNode n = root; n.left != null;) {
      if (n.left.val < low) n.left = n.left.right;
      else n = n.left;
    }
    for (TreeNode n = root; n.right != null;) {
      if (n.right.val > high) n.right = n.right.left;
      else n = n.right;
    }
    return root;
  }
}

struct TreeNode* trimBST(struct TreeNode* root, int low, int high){
  while (root != NULL && (root->val < low || root->val > high)) {
    if (root->val < low) root = root->right;
    else if (root->val > high) root = root->left;
  }
  if (root == NULL) return NULL;
  for (struct TreeNode* n = root; n->left != NULL;) {
    if (n->left->val < low) n->left = n->left->right;
    else n = n->left;
  }
  for (struct TreeNode* n = root; n->right != NULL;) {
    if (n->right->val > high) n->right = n->right->left;
    else n = n->right;
  }
  return root;
}

class Solution {
public:
  TreeNode* trimBST(TreeNode* root, int low, int high) {
    while (root && (root->val < low || root->val > high)) {
      if (root->val < low) root = root->right;
      if (root->val > high) root = root->left;
    }
    if (root == nullptr) return nullptr;
    for (TreeNode* n = root; n->left != nullptr;) {
      if (n->left->val < low) n->left = n->left->right;
      else n = n->left;
    }
    for (TreeNode* n = root; n->right != nullptr;) {
      if (n->right->val > high) n->right = n->right->left;
      else n = n->right;
    }
    return root;
  }
};

class Solution:
  def trimBST(self, root: Optional[TreeNode], low: int, high: int) -> Optional[TreeNode]:
    while root and (root.val < low or root.val > high):
      if root.val < low: root = root.right
      elif root.val > high: root = root.left
    if root == None: return None
    n = root
    while n.left != None:
      if n.left.val < low: n.left = n.left.right
      else: n = n.left
    n = root
    while n.right != None:
      if n.right.val > high: n.right = n.right.left
      else: n = n.right
    return root

迭代 · 前序遍历 · 栈

var trimBST = function(root, low, high) {
  const p = new TreeNode(-1, null, root), stack = [[root, p, 1]]
  while (stack.length > 0) {
    const [n, parent, isRight]  = stack.pop()
    if (n.val < low) isRight ? parent.right = n.right : parent.left = n.right
    else if (n.val > high) isRight ? parent.right = n.left : parent.left = n.left
    if (n.right) {
      if (n.val < low) stack.push([n.right, parent, isRight])
      else if (n.val < high) stack.push([n.right, n, 1])
      else n.right = null
    }
    if (n.left) {
      if (n.val > high) stack.push([n.left, parent, isRight])
      else if (n.val > low) stack.push([n.left, n, 0])
      else n.left = null
    }
  }
  return p.right
};

Shon

Github　力扣　 M站　全部原创，请勿转载

递归，迭代（定长列表 + 位集），3 解法求解《672. 灯泡开关 Ⅱ》

迭代遍历哈希表，求解《828. 统计子串中的唯一字符》

后序遍历，递归和迭代 2 种算法，用哈希映射数据结构，字符串或元组构造键名，用序列化技巧，求解《652. 寻找重复的子树》

后序遍历，递归和迭代 2 种算法，用哈希映射数据结构，字符串 / 元组构造键名，用序列化技巧，求解《652. 寻找重复的子树》