创建一个 returns 新的相同二叉树并向所有 pre-existing 叶子添加新节点的函数

Question

创建一个函数，returns 一个与传入的二叉树相同的新二叉树，除了新树中的每个叶子现在都有左 child 和右 child其值等于 x 和 y。

Answer 1

你很接近。处理扩展的案例是正确的，但你有点搞砸了迭代。这是一个可能的解决方案：

void expand_leaf(TreeNode * node, int x, int y)
{
    // recursively iterate over tree:
    if (node->left)  expand_leaf(node->left, x, y);
    if (node->right) expand_leaf(node->right, x, y);

    // expand leafes:
    if (!node->left && !node->right)
    {
        node->left  = new TreeNode(x, nullptr, nullptr);
        node->right = new TreeNode(y, nullptr, nullptr);
    }
}

你的问题可以优雅地分解为两个sub-problems:

找到树中的所有叶子。
将 children x 和 y 添加到叶子。

找到所有叶子的一种可行方法是遍历树的所有节点并检查它们是否是叶子（如果它们的 left/right 指针为空）。这就是上面 expand_leaf 函数的第一部分所做的：每当 child 指针存在时，它就会被递归访问。这有效地访问了整棵树的所有节点。

现在我们有了访问所有节点的方法，我们可以过滤掉叶子。这就是函数的第二部分所做的。每当我们发现一片叶子时，我们都会向其添加 x/y children。

扩展发生在递归调用之后是非常重要的。否则我们将陷入无限循环。想想为什么。

对原始解决方案的评论

abort condition/base 的情况是需要的并且大部分是正确的，但是您过早地创建了一个新的 TreeNode。如果你随后发现 node==null，你也会用 null 覆盖 just-created n，这会导致内存泄漏。解决方案：将基本情况简化为 if (node == nullptr) return nullptr; 并将 TreeNode * n = new TreeNode; 移动到 if 之后，一旦您知道您正在处理的不是空节点。

其余部分看起来功能正确（没有运行代码）。也许可以进一步提高可读性？

Answer 2

我会这样做：

# define KEY(p) (p->data)
# define LLINK(p) (p->left)
# define RLINK(p) (p->right)

TreeNode * expand_leaf(TreeNode * node, int x, int y)
{
  if (node == nullptr) 
    return nullptr; // copy of empty tree is an empty tree

  TreeNode * root = new TreeNode(KEY(node)); // node copy with its key

  if (LLINK(node) == nullptr and RLINK(node)) // node is leaf? (this is the base case)
    {    // yes ==> create children with x and y
      LLINK(root) = new TreeNode(x);
      RLINK(root) = new TreeNode(y);
      return root;
    }

  LLINK(root) = expand_leaf(LLINK(node), x, y); 
  RLINK(root) = expand_leaf(RLINK(node), x, y);

  return root;
}

为简单起见，我假设 TreeNode class 的构造函数接收密钥。如果你没有，那么你可以添加一个额外的行来设置键值

创建一个 returns 新的相同二叉树并向所有 pre-existing 叶子添加新节点的函数

Creating a function that returns a new identical binary tree and adds new nodes to all pre-existing leaves

c++

tree

binary-tree

对原始解决方案的评论