Leetcode 897：增序搜索树

介绍

  • 在这篇文章中，我们将解决leetcode 897，它主要处理二叉搜索树。
  • 如果你想学习如何操作二叉搜索树中的指针/引用，那么这个问题很好。
  • 我们将研究递归和基于堆栈的解决方案。

问题陈述

  • 我们已经得到了二叉搜索树的根，我们需要以某种方式重新排列它。
  • 根据重新排列，我们将最左边的节点作为树的根，每个节点没有左子节点，只有一个右子节点。

1、递归解决方案
这是递归解决方案的完整代码：

private TreeNode sol2(TreeNode root){
     if(root == null) return null;
     sol2(root.left);
     if(prev!=null){
         root.left = null;
         prev.right = root;
          
     }
     prev = root;
     if(head==null) head = root;
     sol2(root.right);
     return head;
 }


思路：
这个问题的基本直觉是知道我们必须修改树节点的指针/引用

由于对于每个根节点，我们都会查找左侧节点，因此向上查找最左侧节点是有意义的。

if(root == null) return null;
     sol2(root.left);

如果我们位于最左边的节点，那么我们将其初始化为 prev，因为它将在递归调用中有用。

我们还初始化头head节点，因为我们必须返回头节点的引用作为结果。如果我们位于最左边的节点，那么初始化就有意义了。

  prev = root;
  if(head==null) head = root;

如果当前节点不是最左边的节点，那么我们可以执行指针操作。

现在我们将拥有 prev 节点，并且我们将使 prev.right 指向当前根节点。

 if(prev!=null){
         root.left = null;
         prev.right = root;
          
     }

使该节点作为根节点，并且上一个根成为该新根的右子节点。

如果前一个根有右子节点，那么我们再次对该节点进行递归调用，然后像根节点一样遍历最左边的节点。

if(head==null) head = root;
sol2(root.right);
return head;

2、堆栈Stack解决方案
我们还可以使用堆栈数据结构来实现解决方案，其中我们将遍历的节点保留在堆栈中，直到到达最左边的节点。
基本的指针操作逻辑是相同的。

private TreeNode sol1(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;
        while(curr!=null || !stack.isEmpty()){
            while(curr!=null){
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if(prev!=null){
                curr.left=null;
                prev.right = curr;
            }
            if(head==null) head = curr;
            prev = curr;
            curr = curr.right;
        }
         
        return head;
         
    }

复杂

  • 时间复杂度：O(N)，因为我们只访问每个节点一次
  • 空间复杂度：O(H)，其中 H 是树的高度。


在本文中，我们解决了 leetcode 897，这是二叉搜索树上最好解决的问题之一