二叉树的摇摆

Question

Original Problem

问题如前所述，我的解决方案如下： Return BST 树向一个方向摇摆的量。 Sway 由节点数量表示 "unbalanced" - nullptr 仅在一侧，左侧摇摆的树 returns 它摇摆的负数任何向右的摇摆都会抵消向左的摇摆，反之亦然

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;
}

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

二叉树的摇摆

Sway of Binary Tree

tree

recursion

binary-tree