我的天，终于AC了，感动，提交了6次才AC，关键在于一开始想法不对以及初始情况没有处理好。
先介绍一下BFS树，这种树的前序遍历是一个单调递增的序列，左边的值小于根，右边的值大于根。例如下图所示： 寻找key很简单，只要沿着根节点走就行，小的往左走，大的往右走。直至找到key对应的结点指针。 麻烦的是怎么更新一颗树呢？？？ 一开始各种出错的方法就不介绍了，各种反例。。。介绍一下最后AC的方法。
如果要删除的这个结点是个叶子结点，那么直接删就行了如果不是叶子结点，那么需要寻找左边最大值或者右边的最小值。对于上图的根结点5来说，左边的最大值是4，右边的最小值时6。（怎么计算左边的最大值和右边的最小值，就不再论述，有需要的童鞋看看我的代码）。如果找不到右边的最大值，就要找左边的最小值，由于当前要删除的结点不是叶子结点，一定能找到一个满足要求的值。找到之后，交换两者的val就可以了。重复2，直到再叶子结点处删除待删除的结点。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { if(root==NULL) return root; //1 search key TreeNode* tempRoot=root; TreeNode* preRoot=NULL; while(tempRoot!=NULL) { if(key>tempRoot->val) { preRoot=tempRoot; tempRoot=tempRoot->right; } else if(key<tempRoot->val) { preRoot=tempRoot; tempRoot=tempRoot->left; } else break; } //can't find if(tempRoot==NULL) return root; //2 delete tempRoot while(1) { if(tempRoot->left==NULL&&tempRoot->right==NULL) { if(preRoot==NULL) return NULL; if(preRoot->left==tempRoot) preRoot->left=NULL; else if(preRoot->right==tempRoot) preRoot->right=NULL; else{} break; } else { TreeNode* tempSearch; if(tempRoot->right!=NULL) { preRoot=tempRoot; tempSearch=tempRoot->right; while(tempSearch!=NULL&&tempSearch->left!=NULL) { preRoot=tempSearch; tempSearch=tempSearch->left; } } else { preRoot=tempRoot; tempSearch=tempRoot->left; while(tempSearch!=NULL&&tempSearch->right!=NULL) { preRoot=tempSearch; tempSearch=tempSearch->right; } } int temp=tempSearch->val; tempSearch->val=tempRoot->val; tempRoot->val=temp; tempRoot=tempSearch; } } return root; } };