题目:
Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
两个结点被交换过了,那自然而然的想到找出两个结点就行了,而中序遍历又正好是升序序列,因此在中序遍历过程中找到两个不符合升序的结点即可,这里一定要保存一下前驱结点,刚开始没想到,捣鼓了半天过了一半case,后来才发现,代码:
1 void recoverTree(TreeNode *root) { 2 TreeNode* node1; 3 TreeNode* node2; 4 TreeNode* lastNode; 5 node1=NULL; 6 node2=NULL; 7 lastNode=NULL; 8 recoverTree(root,node1,node2,lastNode); 9 if(node1&&node2){ 10 int t=node1->val; 11 node1->val = node2->val; 12 node2->val=t; 13 } 14 } 15 void recoverTree(TreeNode *root,TreeNode*& node1,TreeNode*& node2,TreeNode*& lastNode){ 16 if(root==NULL) return; 17 recoverTree(root->left,node1,node2,lastNode); 18 if(lastNode&&lastNode->val>root->val){ 19 if(!node1) node1=lastNode; 20 node2=root; 21 } 22 lastNode=root; 23 recoverTree(root->right,node1,node2,lastNode); 24 }