Leetcode 之Binary Tree Postorder Traversal（47）

中序遍历二叉搜索树，得到的是一个有序的结果，找出其中逆序的地方就可以了。如果逆序的地方相邻，只需把逆序的相换即可；如果不相邻，则需要找到第二个逆序对的

第二个元素再做交换。

定义两个指针p和q来指定需要交换的元素，指针pre记录当前结点的前驱结点，用来判断是否逆序。

void recoverTree(TreeNode *root)

      {

          pre = p = q = nullptr;

          dfs(root);

          swap(p->val, q->val);

      }

      void dfs(TreeNode *root)

      {

          if (!root)return;

          dfs(root->left);

          if (pre != nullptr && pre->val > root->val)

          {

              if (p == nullptr)

              {

                  p = pre;

                  q = root;

              }

              else

                  q = root;

          }

          pre = root;

          dfs(root->right);

      }

巴特西

Leetcode 之Binary Tree Postorder Traversal（47）

最新文章

热门文章