跳转至

二叉树

94. 二叉树的中序遍历

难度：⭐️

给定一个二叉树的根节点 root ，返回它的 中序 遍历。

解法一 递归

时间复杂度：O(n)
空间复杂度：O(n)

递归 
public List<Integer> inorderTraversal(TreeNode root) {
      List<Integer> res = new ArrayList<>();
      traversal(res, root);
      return res;
  }

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

解法二 迭代

使用栈，循环中将左子树一直入栈，直至叶子结点，访问叶子结点，中间结点，中间结点的右结点。

时间复杂度：O(n)
空间复杂度：O(n)

栈迭代 
  public List<Integer> inorderTraversal(TreeNode root) {
      List<Integer> res = new ArrayList<>();
      LinkedList<TreeNode> stack = new LinkedList<>();
      while(!stack.isEmpty() || root != null) {
          while (root != null) {
              stack.push(root);
              root = root.left;
          }
          root = stack.pop();
          res.add(root.val);
          root = root.right;
      }
      return res;
  }

解法三：Morris 遍历

Morris 遍历的核心思想是建立线索树。遍历过程中，左子树为空时，直接访问该节点；左子树非空时，找到左子树的最右节点，利用叶子节点的右节点临时保存树的结构，第一次遍历先进入左子树，第二次遍历进入右子树。

时间复杂度：O(n)
空间复杂度：O(1)

Morris 遍历 
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode p = root;
        while (p != null) {
            if (p.left == null) {
                list.add(p.val);
                p = p.right;
            } else {
                // 找到左子树的最右节点
                TreeNode pre = p.left;
                while (pre.right != null && pre.right != p) {
                    pre = pre.right;
                }

                if (pre.right == null) {
                    // 第一次遍历，进入左子树
                    pre.right = p;
                    p = p.left;
                } else {
                    // 第二次遍历，进入右子树
                    list.add(p.val);
                    pre.right = null;
                    p = p.right;
                }
            }
        }
        return list;
    }

98. 验证二叉搜索树

难度：⭐️⭐️

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

解法一 递归

按照条件直接递归。

直接递归 
public boolean isValidBST(TreeNode root) {
      if (root == null) {
          return true;
      }
      boolean isLeftBst = true;
      if (root.left != null) {
          int maxLeft = max(root.left);
          if (maxLeft >= root.val) {
              return false;
          }
      }
      if (root.right != null) {
          int minRight = min(root.right);
          if (minRight <= root.val) {
              return false;
          }
      }
      return isValidBST(root.left) && isValidBST(root.right);
  }

  private int min(TreeNode root) {
      if (root == null) {
          return Integer.MAX_VALUE;
      }
      int value = root.val;
      int min = Math.min(min(root.left), min(root.right));
      return Math.min(min, value);
  }

  private int max(TreeNode root) {
      if (root == null) {
          return Integer.MIN_VALUE;
      }
      int value = root.val;
      int max = Math.max(max(root.left), max(root.right));
      return Math.max(max, value);
  }
优化版本的递归

解法二 中序遍历

101. 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

难度：⭐️

解法一 递归

递归检查子树的左右节点是否对称。

递归 
  public boolean isSymmetric(TreeNode root) {
      return root != null && check(root.left, root.right);
  }

  private boolean check(TreeNode left, TreeNode right) {
      if (left == null && right == null) {
          return true;
      } else if (left == null || right == null) {
          return false;
      } else {
          return left.val == right.val && check(left.left, right.right) && check(left.right, right.left);
      }
  }

解法二* 迭代

层次遍历，每次访问2个节点。需要注意的是，层次遍历使用的队列用LinkedList，不要用ArrayDeque，因为ArrayDeque不允许元素为空。

递归 
      public boolean isSymmetric(TreeNode root) {
      if (root.left == null && root.right == null) {
          return true;
      }
      Queue<TreeNode> queue = new LinkedList<>();
      queue.offer(root.left);
      queue.offer(root.right);
      while (!queue.isEmpty()) {
          int size = queue.size();
          for (int i = 0; i < size; i++) {
              TreeNode left = queue.poll();
              TreeNode right = queue.poll();
              if (left == null && right == null) {
                  continue;
              } else if (left != null && right != null) {
                  if (left.val != right.val) {
                      return false;
                  } else {
                      queue.offer(left.left);
                      queue.offer(right.right);
                      queue.offer(left.right);
                      queue.offer(right.left);
                  }
              } else {
                  return false;
              }
          }
      }
      return true;
  }

102. 二叉树的层次遍历

难度：⭐️⭐️

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

方法一 队列

使用队列，第一层循环条件是队列非空，每次进入循环时，队列中恰好是当前层的元素，记录其位置n，遍历队列中n个元素之后，当前层刚好遍历结束。

广度优先层次遍历 
  public List<List<Integer>> levelOrder(TreeNode root) {
      List<List<Integer>> list = new ArrayList<>();
      if (root == null) {
          return list;
      }
      Queue<TreeNode> queue = new LinkedList<>();
      queue.offer(root);
      while (!queue.isEmpty()) {
          int size = queue.size();
          List<Integer> layer = new ArrayList<>();
          for (int i = 0; i < size; i++) {
              TreeNode node = queue.poll();
              layer.add(node.val);
              if (node.left != null) {
                  queue.add(node.left);
              }
              if (node.right != null) {
                  queue.add(node.right);
              }
          }
          if (!layer.isEmpty()) {
              list.add(layer);
          }
      }
      return list;
  }

104. 二叉树的最大深度

难度：⭐️

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

解法一 深度优先

递归 
  public int maxDepth(TreeNode root) {
    return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
  }

解法二 广度优先

层次遍历。使用队列，循环开始时，队列中放的始终是当前层的结点，记录当前层的节点数。遍历的同时，将下一层节点放入队列中。

广度优先遍历 
public int maxDepth(TreeNode root) {
      if (root == null) {
          return 0;
      }
      Queue<TreeNode> queue = new LinkedList<>();
      queue.offer(root);
      int depth = 0;
      while (!queue.isEmpty()) {
          int size = queue.size();
          for (int i = 0; i < size; i++) {
              TreeNode node = queue.poll();
              if (node.left != null) {
                  queue.offer(node.left);
              }
              if (node.right != null) {
                  queue.offer(node.right);
              }
          }
          depth++;
      }
      return depth;
  }

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

难度：⭐️⭐️⭐️⭐️

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

解法一 递归

前序数组的第一个元素是根节点，找到根节点在中序数组的下标，对数组进行拆分。

递归 
  public TreeNode buildTree(int[] preorder, int[] inorder) {
      return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
  }

  private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
      if (preStart > preEnd) {
          return null;
      }
      TreeNode root = new TreeNode(preorder[preStart]);
      int mid = inStart;
      while (inorder[mid] != root.val) {
          mid++;
      }
      int leftLength = mid - inStart;
      int rightSize = inEnd - mid;
      //[ [...] mid [...]]
      root.left = buildTree(preorder, preStart + 1, preStart + leftLength, inorder, inStart, mid - 1);
      root.right = buildTree(preorder, preStart + 1 + leftLength, preEnd, inorder, mid + 1, inEnd);
      return root;
  }

也可以使用哈希表保存下标，避免每次循环找根节点的index

递归 + 哈希表 
  private Map<Integer, Integer> map; // 使用哈希表保存下标

  public TreeNode buildTree(int[] preorder, int[] inorder) {
      map = new HashMap<>(inorder.length);
      for (int i = 0; i < inorder.length; i++) {
          map.put(inorder[i], i);
      }
      return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
  }

  private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
      if (preStart > preEnd) {
          return null;
      }
      TreeNode root = new TreeNode(preorder[preStart]);
      int mid = map.get(root.val);
      int leftLength = mid - inStart;
      int rightSize = inEnd - mid;
      //[ [...] mid [...]]
      root.left = buildTree(preorder, preStart + 1, preStart + leftLength, inorder, inStart, mid - 1);
      root.right = buildTree(preorder, preStart + 1 + leftLength, preEnd, inorder, mid + 1, inEnd);
      return root;
  }

108. 有序数组转二叉搜索树

难度：⭐️

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

解法一 中序遍历

平衡二叉搜索树的根节点一定在数字的中间位置，因此递归将数字不断拆分即可得到平衡二叉树。

中序遍历 
  public TreeNode sortedArrayToBST(int[] nums) {
      return bst(nums, 0, nums.length - 1);
  }

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

114. 二叉树展开为链表

难度：⭐️⭐️

给你二叉树的根结点 root ，请你将它展开为一个单链表：

  • 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  • 展开后的单链表应该与二叉树 先序遍历 顺序相同。

示例 1：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [0]
输出：[0]

提示：

  • 树中结点数在范围 [0, 2000] 内
  • -100 <= Node.val <= 100

解法一 先序遍历

使用栈，先序遍历二叉树。可以使用额外的占位节点作为链表的头，遍历过程中，入栈顺序要按照根、右、左。

时间复杂度：O(n)
空间复杂度：O(n)

非递归先序遍历 
  public void flatten(TreeNode root) {
      if (root == null) {
          return;
      }
      TreeNode dummy = new TreeNode(-1);
      TreeNode p = dummy;
      dummy.right = root;
      Deque<TreeNode> stack = new LinkedList<>();
      stack.push(root);
      while(!stack.isEmpty()) {
          TreeNode node = stack.pop();
          p.right = node;
          p.left = null;
          if (node.right != null) {
              stack.push(node.right);
          }
          if (node.left != null) {
              stack.push(node.left);
          }
          p = p.right;
      }
  }

解法二 递归保存顺序

使用递归遍历， 保存节点到list中，再根据list构建列表。

时间复杂度：O(n)
空间复杂度：O(n)

非递归先序遍历和展开同时进行 
  public void flatten(TreeNode root) {
      List<TreeNode> list = new ArrayList<>();
      inorder(root, list);
      TreeNode p = new TreeNode();
      for (TreeNode node: list) {
          p.left = null;
          p.right = node;
          p = p.right;
      }
  }

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

解法三 Morris 遍历

对于一个节点，如果其有左子树，找到左子树的最右节点（前驱节点），把右子树接到前驱节点的右子树上，再将左子树移动到右边。

时间复杂度：O(n)
空间复杂度：O(1)

Morris 遍历 
  public void flatten(TreeNode root) {
      TreeNode cur = root;
      while (cur != null) {
          if (cur.left != null) {
              // 找到左子树的最右节点
              TreeNode next = cur.left;
              TreeNode prev = next;
              while (prev.right != null) {
                  prev = prev.right;
              }
              // 将当前右子树接到前驱节点的右子树上
              prev.right = cur.right;
              // 将左子树移到右边
              cur.right = next;
              cur.left = null;
          }
          cur = cur.right;
      }
  }

124. 二叉树中的最大路径和

难度：⭐️⭐️⭐️⭐️

二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

路径和 是路径中各节点值的总和。

给你一个二叉树的根节点 · ，返回其 最大路径和 。

解法一 递归

递归分别看左子树和右子树的最大路径和，遍历过程中，将最大值保存。

递归 
  int max = Integer.MIN_VALUE;

  public int maxPathSum(TreeNode root) {
      max(root);
      return max;
  }

  private int max(TreeNode root) {
      if (root == null) {
          return 0;
      }
      int left = 0;
      if (root.left != null) {
          // 最大值有可能是负值，如果为负值，忽略
          left = Math.max(max(root.left), 0);
      }
      int right = 0;
      if (root.right != null) { 
          // 最大值有可能是负值，如果为负值，忽略
          right =  Math.max(max(root.right), 0);
      }
      // 递归过程中，保存最大值
      max = Math.max(max, left + right + root.val);
      return root.val + Math.max(left, right);
  }

199. 二叉树的右视图

难度：⭐️⭐️

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

解法一 非递归深度优先

深度优先前序遍历，使用哈希表保存遍历到的每一层的深度和第一个访问到的节点。

哈希表 + 深度优先 
  public List<Integer> rightSideView(TreeNode root) {
      if (root == null) {
          return new ArrayList<>();
      }
      Deque<TreeNode> stack = new ArrayDeque<>();
      Deque<Integer> depthStack = new ArrayDeque<>();
      Map<Integer, Integer> map = new LinkedHashMap<>();
      TreeNode p = root;
      stack.push(root);
      depthStack.push(0);
      while(!stack.isEmpty()) {
          TreeNode node = stack.pop();
          int depth = depthStack.pop();
          if (!map.containsKey(depth)) {
              map.put(depth, node.val);
          }
          if (node.left != null) {
              stack.push(node.left);
              depthStack.push(depth + 1);
          }
          if (node.right != null) {
              stack.push(node.right);
              depthStack.push(depth + 1);
          }
      }
      return new ArrayList<>(map.values());
  }

解法二 层次遍历

层次遍历，每一层的最后一个节点即为最右侧节点。

哈希表 + 深度优先 
  public List<Integer> rightSideView(TreeNode root) {
      List<Integer> list = new LinkedList<>();
      if (root == null) {
          return list;
      }
      Queue<TreeNode> queue = new LinkedList<>();
      queue.offer(root);
      while(!queue.isEmpty()) {
          int size = queue.size();
          for (int i = 0; i < size; i++) {
              TreeNode node = queue.poll();
              if (i == size - 1) {
                  list.add(node.val);
              }
              if (node.left != null) {
                  queue.offer(node.left);
              }
              if (node.right != null) {
                  queue.offer(node.right);
              }
          }
      }
      return list;
  }

解法三 递归 + 深度遍历

递归遍历的过程中，记录层数。

226. 翻转二叉树

难度：⭐️

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

方法一 递归

递归 
  public TreeNode invertTree(TreeNode root) {
      if (root == null) {
          return root;
      }
      TreeNode left = invertTree(root.right);
      TreeNode right = invertTree(root.left);
      root.left = left;
      root.right = right;
      return root;
  }

解法二 广度优先遍历

层次遍历。仍然使用队列，遍历每一层的每个节点时，将每个节点的左右节点交换。

层次遍历 
  public TreeNode invertTree(TreeNode root) {
      if (root == null) {
          return root;
      }
      Queue<TreeNode> queue = new LinkedList<>();
      queue.offer(root);
      while (!queue.isEmpty()) {
          int size = queue.size();
          for (int i = 0; i < size; i++) {
              TreeNode node = queue.poll();
              TreeNode temp = node.left;
              node.left = node.right;
              node.right = temp;

              if (node.left != null) {
                  queue.offer(node.left);
              }

              if (node.right != null) {
                  queue.offer(node.right);
              }
          }
      }
      return root;
 }

230. 二叉搜索树中第 K 小的元素

难度：⭐️⭐️

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。

示例 1：

输入：root = [3,1,4,null,2], k = 1
输出：1

示例 2：

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

提示：

树中的节点数为 n 。 1 <= k <= n <= 104 0 <= Node.val <= 104

解法一 非递归中序遍历

二叉搜索树，按照中序遍历，就是从小到大的顺序。

时间复杂度：O(H + k)，最坏O(n)
空间复杂度：O(H)

非递归遍历（栈） 
  public int kthSmallest(TreeNode root, int k) {
      Deque<TreeNode> stack = new ArrayDeque<>();
      int cnt = 0;
      TreeNode p = root;

      while (p != null || !stack.isEmpty()) {
          while (p != null) {
              stack.push(p);
              p = p.left;
          }
          p = stack.pop();
          cnt++;
          if (cnt == k) {
              return p.val;
          }
          p = p.right;
      }
      return -1;
  }

解法二：递归中序遍历

时间复杂度：O(H + k)，最坏O(n)
空间复杂度：O(H)

非递归遍历（栈） 
class Solution {
  private TreeNode result;
  private int index;
  public int kthSmallest(TreeNode root, int k) {

      visit(root, k);
      return result.val;
  }

  private void visit(TreeNode node, int k) {
      if (node == null) {
          return;
      }
      visit(node.left, k);
      index++;
      if (index == k) {
          result = node;
          return;
      }
      visit(node.right, k);
  }
}

解法三：Morris 遍历

Morris 遍历的思路：

  • 左子树为空时直接访问当前节点；
  • 左子树非空时，先找到左子树的最右节点(前驱节点)
  • 前驱节点的右子树为空，则将当前节点右子树放在前驱节点的右子树上，进入左子树
  • 前驱节点的右子树非空，访问当前节点，同时将右子树置空，进入当前节点的右子树；

时间复杂度：O(n)
空间复杂度：O(1)

非递归遍历（栈） 
class Solution {
  public int kthSmallest(TreeNode root, int k) {
      // Morris
      TreeNode cur = root;
      while (cur != null) {
          if (cur.left == null) {
              if (--k == 0) {
                  return cur.val;
              }
              cur = cur.right;
          } else {
              TreeNode pre = cur.left;
              while (pre.right != null && pre.right != cur) {
                  pre = pre.right;
              }
              if (pre.right == null) {
                  pre.right = cur;
                  cur = cur.left;
              } else {
                  pre.right = null;
                  if (--k == 0) {
                      return cur.val;
                  }
                  cur = cur.right;
              }
          }
      }
      return -1;
  }
}

解法四： 计算子树的大小

递归计算子树大小，判断第 K 个元素落在左子树、当前节点、右子树上。如果需要频繁查询，可以给子树大小加一个缓存，避免递归重复计算。

时间复杂度：O(H)
空间复杂度：O(H)

递归计算子树大小 ```java class Solution { public int kthSmallest(TreeNode node, int k) { if (node == null) return -1; int left = size(node.left); if (left + 1 == k) return node.val; if (left >= k) return kthSmallest(node.left, k); return kthSmallest(node.right, k - left - 1); } private int size(TreeNode node) { return node == null ? 0 : 1 + size(node.left) + size(node.right); } } ```

236. 二叉树的最近公共祖先

难度：⭐️⭐️

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

解法一 哈希表

深度遍历，遍历过程中使用哈希表记录每个节点的父节点，根据哈希表查两个节点的父节点，两次分别遍历两个找到公共父节点。

哈希表保存父节点 
      public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      Map<TreeNode, TreeNode> parents = new HashMap<>();
      dfs(root, parents);
      Set<TreeNode> pParents = new HashSet<>();
      while (p != null) {
          pParents.add(p);
          p = parents.get(p);
      }
      while (q != null) {
          if (pParents.contains(q)) {
              return q;
          } else {
              q = parents.get(q);
          }
      }
      return null;
  }

  private void dfs(TreeNode node, Map<TreeNode, TreeNode> parents) {
      if (node != null) {
          if (node.left != null) {
              dfs(node.left, parents);
              parents.put(node.left, node);
          }
          if (node.right != null) {
              dfs(node.right, parents);
              parents.put(node.right, node);
          }
      }
  }

解法二 递归

在左子树和右子树中查找，根据条件返回：

  1. 当root和p、q中任意节点相等时，最近节点为root
  2. 当左子树和右子树中查找的值都非空，说明p、q分别在左子树和右子树中，结果为root
  3. 当左子树或右子树中有一个为空，说明p、q同在另一个子树中，结果为非空的子节点
递归 
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
      if (root == null) return null;
      if (root == p || root == q) return root;
      TreeNode left = lowestCommonAncestor(root.left, p, q);
      TreeNode right = lowestCommonAncestor(root.right, p, q);
      if (left != null && right != null) return root;
      if (left != null) return left;
      return right;
  }

450. 删除二叉搜索树中的节点

难度：⭐️⭐️⭐️⭐️

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

一般来说，删除节点可分为两个步骤：

首先找到需要删除的节点； 如果找到了，删除它。

解法一： 递归

当要删除的元素不在树中时，直接返回根节点。
当要删除的元素在树中，先找到待删除的节点，分三种情况讨论： - 要删除的节点是根节点，直接删除它； - 要删除的节点有一个子树为空，只需要把该节点替换成非空的子树即可完成删除； - 要删除的节点左右子树均非空时，需要找到一个结点，移动到要删除的节点的位置，为了让二叉树尽可能保持平衡，一般是找左子树的最大值或者右子树的最小值。

使用递归解法时，先写递归结束的条件代码会更简洁。

递归 
public TreeNode deleteNode(TreeNode root, int key) {
      if (root == null) {
          return null;
      }
      if (root.val == key) {
          if (root.left == null) {
              return root.right;
          }
          if (root.right == null) {
              return root.left;
          }
          TreeNode pre = root.left;
          while (pre.right != null) {
              pre = pre.right;
          }
          root.val = pre.val;
          root.left = deleteNode(root.left, pre.val);
          return root;
      } else if (key < root.val) {
           root.left = deleteNode(root.left, key);
          return root;
      } else {
          root.right = deleteNode(root.right, key);
          return root;
      }

  }

解法二： 迭代

和递归的方法一样，只不过需要在迭代过程中记录访问到的节点的父节点，删除的时候也需要考虑到删除根节点或者非根节点。

递归 
public TreeNode deleteNode(TreeNode root, int key) {
      if (root == null) {
          return null;
      }
      TreeNode target = root;
      TreeNode parent = null;
      while (target != null && target.val != key) {
          if (key < target.val) {
              parent = target;
              target = target.left;
          } else if (key > target.val) {
              parent = target;
              target = target.right;
          }
      }
      if (target == null) {
          return root;
      }

      if (target.left == null || target.right == null) {
          TreeNode child = null;
          if (target.left == null) {
              child = target.right;
          }
          if (target.right == null) {
              child = target.left;
          }

          if (parent == null) {
              // 删根节点
              return child;    
          } else {
              if (parent.left == target) {
                  parent.left = child;
              } else if (parent.right == target) {
                  parent.right = child;
              }
              return root;
          }
      } else {
          // 找右子树的最小值
          TreeNode successor = target.right;
          TreeNode successorParent = target;
          while (successor.left != null) {
              successorParent = successor;
              successor = successor.left;
          }
          target.val = successor.val;
          if (successorParent.left == successor) {
              successorParent.left = successor.right;
          } else {
              successorParent.right = successor.right;
          }
          return root;
      }
  }

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

难度：⭐⭐

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值。差值是一个正数，其数值等于两值之差的绝对值。

示例 1：

输入：root = [4,2,6,1,3]
输出：1

示例 2：

输入：root = [1,0,48,null,null,12,49]
输出：1

提示：

  • 树中节点的数目范围是 [2, 104]
  • 0 <= Node.val <= 104

解法一 中序遍历

中序遍历二叉搜索树，序列一定是升序的，所以只需要记录遍历的前一个节点即可。 注意对根节点单独处理

二叉搜索树遍历有3种方法：

  • 递归，先遍历左子树，读当前节点，再次遍历右节点。时间和空间复杂度都是 O(n)
  • 栈，先将左子树全入栈，读当前节点，再将右节点入栈。时间和空间复杂度都是 O(n)
  • Morris 遍历，左子树为空直接访问，左子树非空时，先找到左子树的最右侧叶子节点，将当前节点挂在右子树上，并进入当前节点的左子树，第二趟进入右子树。时间复杂度都是 O(n)，空间复杂度是 O(1)
中序遍历-递归 
class Solution {
    private int pre = -1;
    private int min = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        dfs(root);
        return min;
    }

    private void dfs(TreeNode node) {
        if (node == null) {
            return;
        }
        dfs(node.left);
        if (pre < 0) {
            pre = node.val;
        } else {
            min = Math.min(min, node.val - pre);
            pre = node.val;
        }
        dfs(node.right);
    }
}
中序遍历-栈 
class Solution {
    public int getMinimumDifference(TreeNode root) {
        int min = Integer.MAX_VALUE;
        int pre = -1;
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode p = root;
        while (p != null || !stack.isEmpty()) {
            while (p != null) {
                stack.push(p);
                p = p.left;
            }
            p = stack.pop();
            if (pre < 0) {
                pre = p.val;
            } else {
                min = Math.min(p.val - pre, min);
                pre = p.val;
            }
            p = p.right;
        }
        return min;
    }
}
中序遍历-Morris 
class Solution {
    public int getMinimumDifference(TreeNode root) {
        int min = Integer.MAX_VALUE;
        int preVal = -1;
        TreeNode cur = root;
        while (cur != null) {
            if (cur.left == null) {
                if (preVal != -1) {
                    min = Math.min(cur.val - preVal, min);
                }
                preVal = cur.val;
                cur = cur.right;
            } else {
                TreeNode pre = cur.left;
                while (pre.right != null && pre.right != cur) {
                    pre = pre.right;
                }
                if (pre.right == null) {
                    pre.right = cur;
                    cur = cur.left;
                } else {
                    if (preVal != -1) {
                        min = Math.min(cur.val - preVal, min);
                    }
                    preVal = cur.val;
                    cur = cur.right;
                    pre.right = null;

                }
            }
        }
        return min;
    }
}

543. 二叉树的直径

难度：⭐️⭐️

给你一棵二叉树的根节点，返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

两节点之间路径的 长度 由它们之间边数表示。

示例 1：

输入：root = [1,2,3,4,5]
输出：3
解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2：

输入：root = [1,2] 输出：1

提示：

  • 树中节点数目在范围 [1, 104] 内
  • -100 <= Node.val <= 100

解法一 深度遍历

递归解法计算二叉树的深度，取左子树和右子树的最大深度之和。由于可能不经过根节点，需要在遍历的过程中记录最大深度。

深度遍历 
  private int d;
  public int diameterOfBinaryTree(TreeNode root) {
      d = 1;
      depth(root);
      return d;
  }

  private int depth(TreeNode root) {
      if (root == null) {
          return 0;
      }
      int left = depth(root.left);
      int right = depth(root.right);
      d = Math.max(d, left + right);
      return 1 + Math.max(left, right);
  }