二叉树 - 二叉搜索树BST - 《LeetCode题目总结》

700. 二叉搜索树中的搜索

单层递归逻辑中，记得return，因为递归有返回值，你不拿到这个返回值，递归没用

    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }
        if (root.val > val) {
            return searchBST(root.left, val);
        }
        if (root.val < val) {
            return searchBST(root.right, val);
        }
        return null;
    }

98. 验证二叉搜索树

递归法转成list
中序遍历将二叉搜索树变成一个list，然后判断这个list是否是有序的即可

class Solution {
    List<Integer> tree = new ArrayList<>();
    public boolean isValidBST(TreeNode root) {
        traversal(root);
        for (int i = 1; i < tree.size(); ++i) {
            if (tree.get(i) <= tree.get(i - 1)) {
                return false;
            }
        }
        return true;
    }
    public void traversal(TreeNode root) {
        if (root == null)  return ;
        traversal(root.left);
        tree.add(root.val);
        traversal(root.right);
    }
}

递归法过程中判断

陷阱1：单层递归逻辑中，不能单纯的比较「左节点小于中间节点」「右节点大于中间节点」。要比较的是「左子树的所有节点小于中间节点」「右子树的所有节点大于中间节点」，如下单层递归逻辑是错误的
```
if (root.val > root.left.val && root.val < root.right.val) {
  return true;
} else {
  return false;
}
```
陷阱2：样例中的最小节点可能是int的最小值，如何初始化比较元素？因为BST中无相等元素，具体得看下面的代码，该代码是错误的，因为如果左子树中的最小节点，有可能是Integer.MIN_VALUE，这样就可能最左叶子节点明明符合要求，只是因为跟对比值相同就被认为是非BST。因此我们取到最左边节点的值来进行比较
```
  int maxVal = Integer.MIN_VALUE;
  public boolean isValidBST(TreeNode root) {
      if (root == null) return true;
      boolean left = isValidBST(root.left);
      if (maxVal < root.val) maxVal = root.val;
      else return false;
      boolean right = isValidBST(root.right);
      return left && right;
  }
```

正确代码

  TreeNode pre = null;
  public boolean isValidBST(TreeNode root) {
      if (root == null) return true;
      boolean left = isValidBST(root.left);
      if (pre != null && pre.val >= root.val) return false;
      pre = root;
      boolean right = isValidBST(root.right);
      return left && right;
  }

530. 二叉搜索树的最小绝对差

迭代法转List
迭代法直接计算

  int res = Integer.MAX_VALUE;
  public int getMinimumDifference(TreeNode root) {
      traversal(root);
      return res;
  }

  TreeNode pre = null;
  public void traversal(TreeNode root) {
      if (root == null) return ;
      traversal(root.left);
      if (pre != null){
          res = Math.min(res, root.val - pre.val);
      }
      pre = root;
      traversal(root.right);
  }

xxx. 二叉树中的众数

「stream的使用和函数式接口的实用」
里面那个判断条件，稍有不慎可能出错，Integer小于127是比较具体的值，大于127比较的是地址，最好使用equals，注释的地方是正确写法。
获得Map后我们希望按照value排序，但是TreeMap只能按照key排序，因此只能用流处理Entry

  public int[] findMode(TreeNode root) {
      List<Integer> list = new ArrayList<>();
      if (root == null) {
          return list.stream().mapToInt(Integer::intValue).toArray();
      }
      Map<Integer, Integer> map = new HashMap<>();
      traversal(root, map);
      List<Map.Entry<Integer, Integer>> mapList = map.entrySet().stream()
              .sorted((c1, c2) -> c2.getValue().compareTo(c1.getValue()))
              .collect(Collectors.toList
      //先把频率最高的一个添加进来，再看看有无频率一样的
      list.add(mapList.get(0).getKey());
      for (int i = 1; i < mapList.size(); ++i) {
          //if (mapList.get(i).getValue().equals(mapList.get(i - 1).getValue()))
          if (mapList.get(i).getValue() == mapList.get(i - 1).getValue()) {
              list.add(mapList.get(i).getKey());
          } else {
              break;
          }
      }
      return list.stream().mapToInt(Integer::intValue).toArray();
  }

  public void traversal(TreeNode root, Map<Integer, Integer> map) {
      if (root == null) return ;
      map.put(root.val, map.getOrDefault(root.val, 0) + 1);
      traversal(root.left, map);
      traversal(root.right, map);
  }

501. 二叉搜索树中的众数

「二叉搜索树的中序遍历是有序数组」
用上一题的方法也可以，但是BST有特殊的性质，考虑能否使用特殊性质，因为中序遍历可以按数值升序获得元素，如果是通常数组，遍历一遍获得最大频率，遍历第二遍获得最大频率对应的元素。因为是有序的，我们可以一边遍历，一边添加元素，如果出现了新的最大频率，清空数组，重新来

  int count = 0; //实时统计频率
  int maxCount = 0; //最大频率
  TreeNode pre = null; //前一个节点
  List<Integer> res = new ArrayList<>();
  public void traversal(TreeNode root){
      if (root == null) return ;
      traversal(root.left);

      if (pre == null) {
          count = 1;
      }else if (pre.val == root.val){
          count ++;
      }else {
          count = 1;
      }
      pre = root;

      if (count == maxCount) {
          res.add(root.val);
      } else if (count > maxCount) {
          maxCount = count;
          res.clear();
          res.add(root.val);
      }

      traversal(root.right);
  }

  public int[] findMode(TreeNode root){
      traversal(root);
      return res.stream().mapToInt(Integer::intValue).toArray();
  }

分析
首先应该想到自底向上进行遍历，因此想到回溯，而后序遍历就是天然的回溯，先处理叶子节点再处理根节点。
接下来如何判断一个节点是p和q的公共祖先，（1）如果一个节点，他的左子树中出现节点p，右子树中出现节点q，或者反过来，则该节点就是p和q的公共祖先（2）节点本身是p，他有一个子孙节点q，也就是说，p本身就是最近公共祖先，这种情况，如果碰到的节点是p或者q，直接返回p或者q就可以了，不需要递归该子树。原因：假设递归到节点p，如果他的左右子树中还有q，拿直接返回p是正确的；如果p的子树中没有q，而q在p的上面，那后序遍历肯定是后遍历到q，这样「如果碰到的节点是p或者q，直接返回p或者q就可以了」再次生效，q覆盖p，则直接返回q仍然是正确的。
为什么该题，递归函数有返回值，仍需要遍历整个树呢？因为采用的是后序遍历，如果想使用左右子树递归的结果，必须左右子树全处理完才行，这样实际上就等于遍历了整个树。也就是下面的单层递归逻辑，要判断左右子树的返回值，根据返回值处理逻辑。
递归的三部曲

递归函数返回值及参数
- TreeNode func(TreeNode root, TreeNode p, TreeNode q)
递归终止条件
- if (root == q || root == p || root == NULL) return root;
单层递归逻辑
- 如果左右子树均不为空，则返回当前节点，root即为最近公共节点
- 如果左子树不为空，右子树为空，则返回right，说明左边没有，是从右边返回上来的
- 如果右子树不为空，左子树为空，则返回left
- 如果左右子树都为空，返回空
```
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
   if (root == p || root == q || root == null) {
       return root;
   }
   TreeNode left = lowestCommonAncestor(root.left, p, q);
   TreeNode 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;
   }
}
```
  235. 二叉搜索树的最近公共祖先
  同上题一样也可以解，但是要利用二叉搜索树的特性，如何判断一个节点的左子树里有p，右子树里有q呢，根据二叉搜索树，当前节点的值p < cur.val < q。
  同时该题要找根节点的值是否满足p < cur.val < q，因此采用从上到下的遍历，而上一题要判断叶子节点是否包含pq，要从下往上的遍历。
  为什么不能在中注释的位置添加if(p.val <= root.val && root.val <= q.val) return root;，因为p和q的大小关系是不确定的，你这样返回肯定出错。所以把返回放到判断条件之外，这样不管是p大还是q大，此时root都在pq之间了。
  另一个问题就是，为什么同样是有返回值的递归，这个题就是找一条路径找到了就直接返回呢，而上一题却要遍历整个树，这是跟遍历的顺序有关的，该题是先序遍历，从上到下，上题是后序遍历，从下到上。因此递归有返回值是搜索一条路径，无返回值是遍历整个树这个说法，不全对。
```
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
   if (root == null) {
       return root;
   }
   //中：根节点

   //左：左子树
   if (root.val > p.val && root.val > q.val) {
       //说明pq在root的左子树中
       TreeNode left = lowestCommonAncestor(root.left, p, q);
       if (left != null) {
           return left;
       }
   }
   //右：右子树
   if (root.val < p.val && root.val < q.val){
       TreeNode right = lowestCommonAncestor(root.right, p, q);
       if (right != null) {
           return right;
       }
   }

   return root;
}
```
  701. 二叉搜索树中的插入操作
递归法有返回值
- 递归函数参数及返回值：有返回值的话，可以利用返回值完成新加入的节点与其父节点的赋值操作
- 递归终止条件：找到遍历的节点为null的时候，就是要插入节点的位置了，并把插入的节点返回，把添加的节点返回给上一层，就完成了父子节点的赋值操作了
- 单层递归逻辑：根据插入元素的数值，决定递归的方向。通过递归函数返回值完成了新加入节点的父子关系赋值操作，下一层将加入节点返回，本层用root->left或者root->right将其接住
```
public TreeNode insertIntoBST(TreeNode root, int val) {
   if (root == null) {
       return new TreeNode(val);
   }
   if (root.val > val) {
       root.left = insertIntoBST(root.left, val);
   }
   if (root.val < val) {
       root.right = insertIntoBST(root.right, val);
   }
   return root;
}
```
递归法无返回值
- 递归函数参数及返回值：无返回值，则需要记录当前节点的父节点，直接让父节点指向插入节点结束递归即可
迭代法
- 也是需要记录当前节点及其父节点
  450. 删除二叉搜索树中的节点
递归参数及返回值
- 上一题中通过返回值插入节点，该题也可通过返回值删除节点
- TreeNode deleteNode(TreeNode root, int key)
递归终止条件
- if(root == null) return root;
单层递归逻辑
- 没找到删除节点，遇到空节点直接返回
- 找到删除节点
  - 左右孩子都为空，则直接删除该节点，同时返回null作为根节点
  - 左节点为空，右节点不为空，删除节点后，右节点补位即可，返回右节点作为根节点
  - 右节点为空，左节点不为空，删除节点后，左节点补位即可，返回左节点作为根节点
  - 左右孩子都不为空，则删除当前节点的话，需要把当前节点的左子树全部移动到右子树的最左下角，返回删除节点的右子树为新的根节点
```
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root;
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 { //root.left != null && root.right != null
    TreeNode cur = root.right;
    while(cur.left != null){
        cur = cur.left;
    }
    cur.left = root.left;
    root = root.right;
    return root;
}
}
if (root.val > key) {
root.left = deleteNode(root.left, key);
}
if (root.val < key) {
root.right = deleteNode(root.right, key);
}
return root;
}
```
    669. 修剪二叉搜索树
    朴素的想法
    if(root == null || root.val < low || root.val > high) return null;但是如果当前节点比low小，他的右子树可能有比low大的值，也可能没有，比high大的情况同理，如果所示，如果是这种逻辑，遇到0节点时，直接整个子树都被砍了
    
    所以遇到在low high之内的节点，应该删除节点，而不应该删除子树
递归函数参数及返回值
- 同上两题，仍然有返回值方便修改
递归终止条件
- 空节点返回
单层递归逻辑
- 如果当前节点元素小于low的值，左子树直接砍掉，所以应该递归调用右子树，并返回右子树中符合条件的头节点
- 如果当前节点元素大于high的值，右子树直接砍掉，所以应该递归调用左子树，并返回左子树中符合条件的头节点
- 接下来，将递归调用左子树的结果赋给左孩子，递归右子树结果赋给右孩子
```
public TreeNode trimBST(TreeNode root, int low, int high) {
if (root == null) return root;
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;
}
```
  108. 将有序数组转换为二叉搜索树
  定义区间为左闭右闭，因此递归终止的条件为left > right ```java public TreeNode sortedArrayToBST(int[] nums) { return buildTree(nums, 0, nums.length - 1); }

public TreeNode buildTree(int[] nums, int left, int right) { if (left > right) { return null; } int mid = left + (right - left >> 1); TreeNode root = new TreeNode(nums[mid]); root.left = buildTree(nums, left, mid - 1); root.right = buildTree( nums, mid + 1, right); return root; }

<a name="wi6h4"></a>
### [538. 把二叉搜索树转换为累加树](https://leetcode.cn/problems/convert-bst-to-greater-tree/)
朴素的想法<br />中序遍历得到有序数组，逆序遍历数组求的累加值，但是如何赋值回去呢<br />边递归边处理<br />根据上面逆序处理数组，因此递归的时候应该逆中序遍历，本题依然需要一个pre指针来指向当前节点的前一个节点的值
```java
    public TreeNode convertBST(TreeNode root) {
        traversal(root);
        return root;
    }

    int pre = 0;
    public void traversal(TreeNode root) {
        if (root == null) return ;
        traversal(root.right);
        root.val += pre;
        pre = root.val;
        traversal(root.left);
    }