这是一个 naive 的做法:
void deleteTreeRec(TreeNode *root){
if (root == NULL) return;
deleteTreeRec(root->left);
deleteTreeRec(root->right);
cout << "Deleting node " << root->data << endl;
delete root;
}
O(1) 空间的做法如下:
把树的左侧节点看成一条链,我们的目的就是不断把当前 root 节点的右子树挪到这条链的末尾,最终可以把这棵树展平为一条链。
而在展开的过程中我们可以删除这条链的头节点(即root节点),最后可以把这条链删除干净。
void deleteTree(TreeNode* root) {
TreeNode* tail = root;
while (root != nullptr){
// update tail
while (tail->left != nullptr) {
tail = tail->left;
}
// move right to the end of the "list"
// needs to happen before retrieving next, since the node may only have a right subtree
tail->left = root->right;
// need to retrieve the data about the next
TreeNode* next = root->left;
delete root;
root = next;
}
}
标签:额外,TreeNode,内存,next,tail,right,二叉树,root,left
From: https://www.cnblogs.com/sparkyen/p/18416267