这是一个创建于 2823 天前的主题，其中的信息可能已经有所发展或是发生改变。
二叉树中很多题目用到递归，比如反转二叉树
public TreeNode invertNode(TreeNode root) {
if(root==null)
return root;
TreeNode temp=root.left;
root.left=invertNode(root.right);
root.right=invertNode(temp);
return root;
}
要怎样去在脑袋里过一遍这段代码的运行过程？
整个过程的栈帧变化是怎样的？
5 条回复 • 2017-03-04 13:37:46 +08:00
 |
1
begeekmyfriend 2017-03-03 21:20:25 +08:00
建议你先看一下我写的《树形结构的调试打印》： https://www.v2ex.com/t/338653
不过里面是非递归用法。你可以随便写一棵二叉树，用递归插入和删除 ```c void insert(struct node **n) { if (*n == NULL) { *n = malloc(); printf(n-->value); } insert(n->left); insert(n->right); } void delete(struct node *n) { if (n != NULL) { delete(n->left); delete(n->right); printf(n->value); free(n); } } // demo insert(tree->root); dump(tree); delete(tree->root); ``` 无需我讲解了，该打印的打印，你就知道为何采用这种顺序。 顺便说一下，删除可以优化 ```c void delete(struct node *n) { if (n->left != NULL) { delete(n->left); } if (n->right != NULL) { delete(n->right); } printf(n->value); free(n); } ``` |
 |
2
ryd994 2017-03-04 07:50:27 +08:00 via Android
栈有什么特别的？不就是调用压返回出么
递归不要关注这种细节 你只需要证明两点： 递归不变式 结束条件 |
 |
3
acumen 2017-03-04 08:47:42 +08:00 via iPhone
楼主的栈帧是指 函数调用栈 吗，和 #2 说法一样，算法本身不关心调用栈，递归应该关心的是递归式子和递归何时结束。
怎么在脑子过这问题的话，递归都一样吧，每次调用记住这个一次调用的状态（该题的话就是二叉树的根和她的左右儿子）。 建议楼主画个图跑一边就清楚了 |
|
4
ryd994 2017-03-04 13:25:25 +08:00
如果你是想把递归解改成非递归的话
其实这里用到的参数只有一个： root 循环过程中维护好这个栈就好 同时，如果你的树里有子到父的回指针的话，不需要栈，因为反正能算出来 这就是 DFS |
 |
5
zhy0216 2017-03-04 13:37:46 +08:00
递归就是要用递归的方式, 不需要栈什么的
我感觉你贴的代码看起来很别扭... https://gist.github.com/zhy0216/c8163b1312bec2185fb55bbbd2df548b 你写这个递归函数的时候, 你就想象这个函数是完成的. 所以你先去反转左子树(函数调用); 再去反转右子树, 因为我们假设这个函数是已经完成了的. 那么左右子树都是交换了的, 那么只用交换左右子树的位置. 这里, 也可以先交换左右子树的位置, 再去反转左右子树. 顺序没关系. |
Select Language