🐶虚拟上门

如果time complexity要求不高的话应该不需要用到morris traversal，用最笨的方法用iterative的方式从root出发去找最左边的子节点，其实就是postorder去找。如果删除到root自己了，就把root改成右节点。时间复杂度O(N * H), 不需要额外memory。

麻烦各位大佬看看，verify一下：

1. void freeTree( TreeNode*& root ) {
   
2.     while ( root != NULL ) {
   
3.         TreeNode* cur = root;
   
4.         TreeNode* parent = NULL;
   
5.         while ( cur->left != NULL ) {
   
6.             parent = cur;
   
7.             cur = cur->left;
   
8.             if ( cur->left == NULL ) {
   
9.                 if ( cur->right != NULL ) {
   
10.                     cur = cur->right;
    
11.                 }
    
12.             }
    
13.         }
    
14.         if ( parent == NULL ) {
    
15.             TreeNode* tmp = root;
    
16.             root = root->right;
    
17.             delete tmp;
    
18.             continue;
    
19.         }
    
20.         if ( parent->left != NULL ) {
    
21.             parent->left = NULL;
    
22.         } else {
    
23.             parent->right = NULL;
    
24.         }
    
25.         delete cur;
    
26.     }
    
27. }
    
28. int main() {
    
29.     TreeNode* root = new TreeNode( -1 );
    
30.     TreeNode* a = new TreeNode( 0 );
    
31.     TreeNode* b = new TreeNode( 1 );
    
32.     TreeNode* c = new TreeNode( 2 );
    
33.     TreeNode* d = new TreeNode( 3 );
    
34.     TreeNode* e = new TreeNode( 4 );
    
35.     TreeNode* f = new TreeNode( 5 );
    
36.     root->left = a;
    
37.     root->right = b;
    
38.     a->left = c;
    
39.     a->right = d;
    
40.     b->left = e;
    
41.     b->right = f;
    
42.     freeTree( root );
    
43.     assert ( root == NULL );
    
44. }

复制代码