二叉树的摇摆

Question

Original Problem

问题如上所述，我的解决方案如下:返回BST树在一个方向上的摇摆量。Sway由“不平衡”的节点量表示- nullptr仅在一侧，左摆动的树返回其摆动的负数，任何右摆动都会偏移左边，反之亦然

int tree_sway(Node * node){
   if(!node){
      return 0;
   }

   int m = tree_sway(node->right) + 1;
   int n =  tree_sway(node->left) - 1;

   return m - n;
}

对于树摇摆问题，我发布的解决方案是否正确？如果不是，解决这个问题的唯一方法是创建一个辅助函数来跟踪递归步骤进行的左转和右转的次数？

Answer 1

您发布的代码不太正确。例如，在具有根和叶的树上，无论叶在哪一侧，结果都将始终为0。其中一种方法是：

int tree_swap(Node *node) {
    # base case of the recursion
    if (!node) { return 0; }

    # go down the left and right branches and add their scores
    int score = tree_swap(node->left) + tree_swap(node->right);

    # adjust the score for the missing children of the current node
    if (!node->left) { score++; }
    if (!node->right) { score--; }
    return score;
}

一般的想法是，当你递归时，你首先沿着树往下走，当你回到树上时，你计算丢失的左右分支，并将运行的计数传递到树上。