码界Musing

迭代与递归的区别

递归：程序调用自身的编程技巧称为递归,是函数自己调用自己.一个函数在其定义中直接或间接调用自身的一种方法,它通常把一个大型的复杂的问题转化为一个与原问题相似的规模较小的问题来解决,可以极大的减少代码量.递归的能力在于用有限的语句来定义对象的无限集合。
迭代：利用变量的原值推算出变量的一个新值.如果递归是自己调用自己的话,迭代就是A不停的调用B。

递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换.能用迭代的不用递归,递归调用函数,浪费空间,并且递归太深容易造成堆栈的溢出。

递归和迭代都是循环的一种。简单地说，递归是重复调用函数自身实现循环。迭代是函数内某段代码实现循环，而迭代与普通循环的区别是：循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。

递归循环中，遇到满足终止条件的情况时逐层返回来结束。迭代则使用计数器结束循环。当然很多情况都是多种循环混合采用，这要根据具体需求。

// 递归
int functionA(int n) {
  if (n>1) {
    return n+functionA(n-1);
  } else {
    return 1;
  }
}

// 迭代
int functionB(int n) {
  int i,s = 0;
  for (i = 1;i < n; i++) {
		s = s + i;
  }
  return s;
}

二叉树的遍历模版

////////1. 递归模版遍历二叉树//////////
public List<Integer> preorderTraversal(TreeNode root) {  
    List<Integer> res = new ArrayList<>();  
  
    preorder(root, res);  
    return res;  
}  
  
private void preorder(TreeNode root, List<Integer> res) {  
    if (root == null) {  
        return;  
    }  
    res.add(root.val);  
    preorder(root.left, res);  
    preorder(root.right, res);  
}  

////////2. 迭代模版遍历二叉树//////////
public class Solution {  
    public List<Integer> preorderTraversal(TreeNode root) {  
        List<Integer> res = new ArrayList<>();  
        if (root == null) {  
            return res; // 二叉树为空直接返回空列表  
        }  
  
        Stack<TreeNode> stack = new Stack<>();  
        stack.push(root);  
  
        while (!stack.isEmpty()) { // 栈不为空  
            TreeNode node = stack.pop(); // 弹出根节点  
            res.add(node.val); // 访问根节点  
  
            // 注意：前序遍历是先左后右，但栈是后入先出，所以要先将右子树入栈，再左子树入栈  
            if (node.right != null) {  
                stack.push(node.right); // 右子树入栈  
            }  
            if (node.left != null) {  
                stack.push(node.left); // 左子树入栈  
            }  
        }  
  
        return res;  
    }  
}

二叉树的前序遍历

二叉树的中序遍历

二叉树的后序遍历

二叉树的前序遍历

// 递归
public class Solution {  
    public List<Integer> preorderTraversal(TreeNode root) {  
        List<Integer> res = new ArrayList<>();  
  
        preorder(root, res);  
        return res;  
    }  
  
    private void preorder(TreeNode root, List<Integer> res) {  
        if (root == null) {  
            return;  
        }  
        res.add(root.val);  
        preorder(root.left, res);  
        preorder(root.right, res);  
    }  

}

// 显式栈
public class Solution {  
    public List<Integer> preorderTraversal(TreeNode root) {  
        List<Integer> res = new ArrayList<>();  
        if (root == null) {  
            return res; // 二叉树为空直接返回空列表  
        }  
  
        Stack<TreeNode> stack = new Stack<>();  
        stack.push(root);  
  
        while (!stack.isEmpty()) { // 栈不为空  
            TreeNode node = stack.pop(); // 弹出根节点  
            res.add(node.val); // 访问根节点  
  
            // 注意：前序遍历是先左后右，但栈是后入先出，所以要先将右子树入栈，再左子树入栈  
            if (node.right != null) {  
                stack.push(node.right); // 右子树入栈  
            }  
            if (node.left != null) {  
                stack.push(node.left); // 左子树入栈  
            }  
        }  
  
        return res;  
    }  
}

二叉树的中序遍历

// 递归
public class Solution {  
    public List<Integer> inorderTraversal(TreeNode root) {  
        List<Integer> res = new ArrayList<>();  
        inorder(root, res);  
        return res;  
    }  
  
    private void inorder(TreeNode root, List<Integer> res) {  
        if (root == null) {  
            return;  
        }  
        inorder(root.left, res);  
        res.add(root.val);  
        inorder(root.right, res);  
    }  
}

// 显式栈
public class Solution {  
    public List<Integer> inorderTraversal(TreeNode root) {  
        List<Integer> res = new ArrayList<>();  
        Stack<TreeNode> stack = new Stack<>();  
        TreeNode curr = root;  
  
        while (curr != null || !stack.isEmpty()) {  
            // 将当前节点的所有左子节点入栈  
            while (curr != null) {  
                stack.push(curr);  
                curr = curr.left;  
            }  
  
            // 栈顶元素出栈，并访问  
            TreeNode node = stack.pop();  
            res.add(node.val);  
  
            // 访问当前节点的右子树  
            curr = node.right;  
        }  
  
        return res;  
    }  
}

二叉树的后序遍历

// 递归
public class Solution {  
    public List<Integer> postorderTraversal(TreeNode root) {  
        List<Integer> res = new ArrayList<>();  
        postorder(root, res);  
        return res;  
    }  
  
    private void postorder(TreeNode root, List<Integer> res) {  
        if (root == null) {  
            return;  
        }  
        postorder(root.left, res);  
        postorder(root.right, res);  
        res.add(root.val);  
    }  
}

// 显式栈
public class Solution {  
    public List<Integer> postorderTraversal(TreeNode root) {  
        List<Integer> res = new ArrayList<>();  
        Stack<TreeNode> stack = new Stack<>();  
        TreeNode prev = null; // 保存前一个访问的节点  
  
        while (root != null || !stack.isEmpty()) {  
            // 将当前节点的所有左子节点入栈  
            while (root != null) {  
                stack.push(root);  
                root = root.left;  
            }  
  
            TreeNode node = stack.pop();  
  
            // 如果当前节点没有右子树，或者右子树已经被访问过  
            if (node.right == null || node.right == prev) {  
                res.add(node.val); // 访问该节点  
                prev = node; // 记录前一节点  
                root = null; // 将当前根节点标记为空，继续外层循环判断  
            } else {  
                stack.push(node); // 右子树尚未访问完毕，将当前节点重新压回栈中  
                root = node.right; // 继续访问右子树  
            }  
        }  
  
        return res;  
    }  
}

二叉树的层序遍历

// 显式栈方式层序遍历
public class Solution {  
    public List<List<Integer>> levelOrder(TreeNode root) {  
        List<List<Integer>> order = new ArrayList<>();  
        if (root == null) {  
            return order;  
        }  
          
        Queue<TreeNode> queue = new LinkedList<>();  
        queue.offer(root);  
          
        while (!queue.isEmpty()) {  
            List<Integer> level = new ArrayList<>();  
            int size = queue.size();  
              
            for (int i = 0; i < size; i++) {  
                TreeNode curr = queue.poll();  
                level.add(curr.val);  
                  
                if (curr.left != null) {  
                    queue.offer(curr.left);  
                }  
                  
                if (curr.right != null) {  
                    queue.offer(curr.right);  
                }  
            }  
              
            if (!level.isEmpty()) {  
                order.add(level);  
            }  
        }  
          
        return order;  
    }  
}

二叉树的锯齿形层序遍历

// 广度优先搜索
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<List<Integer>>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();
        nodeQueue.offer(root);
        boolean isOrderLeft = true;

        while (!nodeQueue.isEmpty()) {
            Deque<Integer> levelList = new LinkedList<Integer>();
            int size = nodeQueue.size();
            for (int i = 0; i < size; ++i) {
                TreeNode curNode = nodeQueue.poll();
                if (isOrderLeft) {
                    levelList.offerLast(curNode.val);
                } else {
                    levelList.offerFirst(curNode.val);
                }
                if (curNode.left != null) {
                    nodeQueue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    nodeQueue.offer(curNode.right);
                }
            }
            ans.add(new LinkedList<Integer>(levelList));
            isOrderLeft = !isOrderLeft;
        }

        return ans;
    }
}

二叉树的层序遍历 II

// 自上向下的层序遍历
class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> levelOrder = new LinkedList<List<Integer>>();
        if (root == null) {
            return levelOrder;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                TreeNode left = node.left, right = node.right;
                if (left != null) {
                    queue.offer(left);
                }
                if (right != null) {
                    queue.offer(right);
                }
            }
            levelOrder.add(0, level);// 头插法
        }
        return levelOrder;
    }
}

二叉树的最大深度

// 深度优先搜索
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth(root.left);
            int rightHeight = maxDepth(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

// 广度优先搜索
class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            ans++;
        }
        return ans;
    }
}

二叉树的最小深度

// 深度优先搜索
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        if (root.left == null && root.right == null) {
            return 1;
        }

        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }

        return min_depth + 1;
    }
}

// 广度优先搜索
class Solution {
    class QueueNode {
        TreeNode node;
        int depth;

        public QueueNode(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        Queue<QueueNode> queue = new LinkedList<QueueNode>();
        queue.offer(new QueueNode(root, 1));
        while (!queue.isEmpty()) {
            QueueNode nodeDepth = queue.poll();
            TreeNode node = nodeDepth.node;
            int depth = nodeDepth.depth;
            if (node.left == null && node.right == null) {
                return depth;
            }
            if (node.left != null) {
                queue.offer(new QueueNode(node.left, depth + 1));
            }
            if (node.right != null) {
                queue.offer(new QueueNode(node.right, depth + 1));
            }
        }

        return 0;
    }
}

路径总和

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }
}

路径总和 II

// 深度优先搜索
class Solution {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Deque<Integer> path = new LinkedList<Integer>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return ret;
    }

    public void dfs(TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        path.offerLast(root.val);
        targetSum -= root.val;
        if (root.left == null && root.right == null && targetSum == 0) {
            ret.add(new LinkedList<Integer>(path));
        }
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);
        path.pollLast();
    }
}

// 广度优先搜索
class Solution {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queueNode = new LinkedList<TreeNode>();
        Queue<Integer> queueSum = new LinkedList<Integer>();
        queueNode.offer(root);
        queueSum.offer(0);

        while (!queueNode.isEmpty()) {
            TreeNode node = queueNode.poll();
            int rec = queueSum.poll() + node.val;

            if (node.left == null && node.right == null) {
                if (rec == targetSum) {
                    getPath(node);
                }
            } else {
                if (node.left != null) {
                    map.put(node.left, node);
                    queueNode.offer(node.left);
                    queueSum.offer(rec);
                }
                if (node.right != null) {
                    map.put(node.right, node);
                    queueNode.offer(node.right);
                    queueSum.offer(rec);
                }
            }
        }

        return ret;
    }

    public void getPath(TreeNode node) {
        List<Integer> temp = new LinkedList<Integer>();
        while (node != null) {
            temp.add(node.val);
            node = map.get(node);
        }
        Collections.reverse(temp);
        ret.add(new LinkedList<Integer>(temp));
    }
}

二叉树中的最大路径和

class Solution {
    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        maxGain(root);
        return maxSum;
    }

    public int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值
        int priceNewpath = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, priceNewpath);

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }
}

对称二叉树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        return check(root,root);
    }
    public boolean check(TreeNode u,TreeNode v) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(u);
        q.offer(v);

        while (!q.isEmpty()) {
            u = q.poll();
            v = q.poll();
            if (u == null && v == null) {
                continue;
            }
            if ((u == null || v == null) || (u.val != v.val)) {
                return false;
            }
            q.offer(u.left);
            q.offer(v.right);

            q.offer(u.right);
            q.offer(v.left);
        }
        return true;
    }
}

二叉树的最近公共祖先

class Solution {

    private TreeNode ans;

    public Solution() {
        this.ans = null;
    }

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            ans = root;
        } 
        return lson || rson || (root.val == p.val || root.val == q.val);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return this.ans;
    }
}

二叉树的右视图

// 深度优先搜索
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
        int max_depth = -1;

        Deque<TreeNode> nodeStack = new LinkedList<TreeNode>();
        Deque<Integer> depthStack = new LinkedList<Integer>();
        nodeStack.push(root);
        depthStack.push(0);

        while (!nodeStack.isEmpty()) {
            TreeNode node = nodeStack.pop();
            int depth = depthStack.pop();

            if (node != null) {
            	// 维护二叉树的最大深度
                max_depth = Math.max(max_depth, depth);

                // 如果不存在对应深度的节点我们才插入
                if (!rightmostValueAtDepth.containsKey(depth)) {
                    rightmostValueAtDepth.put(depth, node.val);
                }

                nodeStack.push(node.left);
                nodeStack.push(node.right);
                depthStack.push(depth + 1);
                depthStack.push(depth + 1);
            }
        }

        List<Integer> rightView = new ArrayList<Integer>();
        for (int depth = 0; depth <= max_depth; depth++) {
            rightView.add(rightmostValueAtDepth.get(depth));
        }

        return rightView;
    }
}

// 广度优先搜索
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
        int max_depth = -1;

        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        Queue<Integer> depthQueue = new LinkedList<Integer>();
        nodeQueue.add(root);
        depthQueue.add(0);

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.remove();
            int depth = depthQueue.remove();

            if (node != null) {
            	// 维护二叉树的最大深度
                max_depth = Math.max(max_depth, depth);

                // 由于每一层最后一个访问到的节点才是我们要的答案，因此不断更新对应深度的信息即可
                rightmostValueAtDepth.put(depth, node.val);

                nodeQueue.add(node.left);
                nodeQueue.add(node.right);
                depthQueue.add(depth + 1);
                depthQueue.add(depth + 1);
            }
        }

        List<Integer> rightView = new ArrayList<Integer>();
        for (int depth = 0; depth <= max_depth; depth++) {
            rightView.add(rightmostValueAtDepth.get(depth));
        }

        return rightView;
    }
}

翻转二叉树

class Solution {
    // 交换root节点的两个子节点
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right ;
        root.right = left;
        return root;
    }
}

二叉树的完全性检验

1
2
3

```
## 另一棵树的子树
```java

相同的树

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
}

填充每个节点的下一个右侧节点指针

1
2
3

```
## 填充每个节点的下一个右侧节点指针 II 
```java

二叉树的序列化和反序列化

```
## 二叉树展开为链表
```java
// 二叉树展开为链表
class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
      	// 前序遍历将二叉树修改为链表
        preorderTraversal(root, list);
        int size = list.size();
        for (int i = 1; i < size; i++) {
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }

    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
        if (root != null) {
            list.add(root);
            preorderTraversal(root.left, list);
            preorderTraversal(root.right, list);
        }
    }
}

从前序与中序遍历序列构造二叉树

前序遍历：根左右；

中序遍历：左根右；

举例：

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

// 递归
class Solution {
    private Map<Integer, Integer> indexMap;

    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }

        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);
        
        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
}

// 迭代（可选）
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
      	// 1. 前序遍历的头，就是整棵树的根节点 
        TreeNode root = new TreeNode(preorder[0]);
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        int inorderIndex = 0;
        for (int i = 1; i < preorder.length; i++) {
            int preorderVal = preorder[i];
            TreeNode node = stack.peek();
          	// 2. node 存在左子节点
            if (node.val != inorder[inorderIndex]) {
                node.left = new TreeNode(preorderVal);
                stack.push(node.left);
            } else {
                while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
                    node = stack.pop();
                    inorderIndex++;
                }
                node.right = new TreeNode(preorderVal);
                stack.push(node.right);
            }
        }
        return root;
    }
}

验证二叉搜索树

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
    }
}

二叉搜索树迭代器

class BSTIterator {
    private int idx;
    private List<Integer> arr;

    public BSTIterator(TreeNode root) {
        idx = 0;
        arr = new ArrayList<Integer>();
        inorderTraversal(root, arr);
    }

    public int next() {
        return arr.get(idx++);
    }

    public boolean hasNext() {
        return idx < arr.size();
    }

    private void inorderTraversal(TreeNode root, List<Integer> arr) {
        if (root == null) {
            return;
        }
        inorderTraversal(root.left, arr);
        arr.add(root.val);
        inorderTraversal(root.right, arr);
    }
}

二叉搜索树中的搜索

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (val == root.val) {
            return root;
        }
        return searchBST(val < root.val ? root.left : root.right, val);
    }
}

二叉搜索树中的插入操作

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        TreeNode pos = root;
        while (pos != null) {
            if (val < pos.val) {
                if (pos.left == null) {
                    pos.left = new TreeNode(val);
                    break;
                } else {
                    pos = pos.left;
                }
            } else {
                if (pos.right == null) {
                    pos.right = new TreeNode(val);
                    break;
                } else {
                    pos = pos.right;
                }
            }
        }
        return root;
    }
}

删除二叉搜索树中的节点

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        if (root.val > key) {
            root.left = deleteNode(root.left, key);
            return root;
        }
        if (root.val < key) {
            root.right = deleteNode(root.right, key);
            return root;
        }
        if (root.val == key) {
            if (root.left == null && root.right == null) {
                return null;
            }
            if (root.right == null) {
                return root.left;
            }
            if (root.left == null) {
                return root.right;
            }
            TreeNode successor = root.right;
            while (successor.left != null) {
                successor = successor.left;
            }
            root.right = deleteNode(root.right, successor.val);
            successor.right = root.right;
            successor.left = root.left;
            return successor;
        }
        return root;
    }
}