c++ - 如何反转二叉搜索树？

Question

问题:https://leetcode.com/problems/invert-binary-tree/

我的方法:

void getInorder(std::vector<int> & vec, TreeNode* root){
        if(root){
            getInorder(vec, root->left);
            vec.push_back(root->val);
            getInorder(vec, root->right);
        }
    }

    void setValues(TreeNode*  root, std::vector<int> &vec, int &i ){
        if(root){
            setValues(root->left, vec, i);
            root->val = vec[i];
            i--;
            setValues(root->right, vec, i);
        }
    }

    TreeNode* invertTree(TreeNode* root) {
        std::vector<int> inorderList, sol;
        getInorder(inorderList, root);
        int  i = inorderList.size() - 1;
        setValues(root, inorderList, i);
        getInorder(sol, root);
        return root;
    }

我按顺序遍历树，并记下列表中的值。我再次按顺序遍历树，但这次我开始从列表末尾开始将值分配给节点。这应该交换左右子值，从而在您再次执行排序时提供递减序列。

测试用例 [1,2] 失败。根据它输出 [2,1] 的逻辑，这对我来说似乎是正确的，但实际输出是 [1, null, 2]。我猜leetcode是对输出做前序遍历，不是很清楚。

我该如何解决这个问题？

Answer 1

代码只改变了val字段，没有改变原来的拓扑结构。所以一棵树看起来像:

  1
 / \
2   5
   / \
  3   4

可以只改变值，这样中序遍历会产生一个反转的列表:

  5
 / \
4   3
   / \
  1   2

这看起来用二叉搜索树好多了，但这不是最初的问题描述。对于 BST，这种反转会产生具有反转比较运算符的 BST。

幸运的是，通常树反转意味着树的完全反转，包括它的拓扑结构。幸运的是，因为获得完全反转比仅仅值反转更容易编码。在上面的示例中，原始结果的完全反转:

    1
   / \
  5   2
 / \
4   3

要做到这一点，您需要停止使用 vector 并停止收集值。该算法成为一个简单的单函数递归算法。它可以用一个主体为 6 行的函数来完成。

但是如果你想创建一个反向拷贝，而不改变原始树，那么它就变成了一个 7 行主体。