将二叉树中的每个节点替换为其有序前驱和后继的总和

Question

我试图在不使用数组的情况下解决这个问题：

Node replaceWithSum(Node root) {
   if (root == null) {
      return null;
   }

   Queue<Node> q = new LinkedList();
   q.add(root);

   Node predecessor, successor = null;
   while(!q.isEmpty()) {
      Node node = q.peek();
      q.remove();

      predecessor = node.left; //possible predecessor
      successor = node.right; //possible successor

      while (predecessor != null && predecessor.right != null) {
           predecessor = predecessor.right;
      }

      while (successor != null && successor.left != null) {
           successor = successor.left;
      }

      node.data = ((predecessor != null)? predecessor.data : 0) + ((successor != null)? 
                                                                   successor.data : 0)


      if (node.left != null) {
         q.add(node.left)
      } 
      if (node.right != null) {
         q.add(node.right)
      }
   }

   return root;
}

使用队列按级别顺序遍历。我理解 space 复杂度为 O(n)。你能帮我理解这个问题的时间复杂度吗？如果树是倾斜的，当我们只为一个节点找到 predecessor/successor 时，最坏的情况是可能的。这个问题的最坏情况是树是平衡的，时间复杂度也是 O(nlogn)？

提前致谢！

Answer 1

时间复杂度为O(n)。这有点像构建一个堆。

假设您有一个高度为 h 的完整二叉树。

你从根到叶，假设k是层，它从0到h-1。

在级别 k，您有 2^k 个节点。对于每个节点，最多需要访问h-k个节点来找到它的前驱和后继。

通过wolframalpha，我们可以得到这个公式：

显然，它等于 O(n)。

将二叉树中的每个节点替换为其有序前驱和后继的总和

Replace each node in binary tree with the sum of its inorder predecessor and successor

algorithm

tree

binary-tree

data-structures