二叉树中的递归有点难以理解，求解答？

[uuweZhou]

二叉树中很多题目用到递归，比如反转二叉树

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;  
    }  

要怎样去在脑袋里过一遍这段代码的运行过程？

整个过程的栈帧变化是怎样的？

[begeekmyfriend]

建议你先看一下我写的《树形结构的调试打印》： 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);
}
```

[ryd994]

栈有什么特别的？不就是调用压返回出么
递归不要关注这种细节
你只需要证明两点：
递归不变式
结束条件

[acumen]

楼主的栈帧是指 函数调用栈 吗，和 #2 说法一样，算法本身不关心调用栈，递归应该关心的是递归式子和递归何时结束。
怎么在脑子过这问题的话，递归都一样吧，每次调用记住这个一次调用的状态（该题的话就是二叉树的根和她的左右儿子）。
建议楼主画个图跑一边就清楚了

[ryd994]

如果你是想把递归解改成非递归的话
其实这里用到的参数只有一个： root
循环过程中维护好这个栈就好
同时，如果你的树里有子到父的回指针的话，不需要栈，因为反正能算出来
这就是 DFS

[zhy0216]

递归就是要用递归的方式, 不需要栈什么的

我感觉你贴的代码看起来很别扭...

https://gist.github.com/zhy0216/c8163b1312bec2185fb55bbbd2df548b

你写这个递归函数的时候, 你就想象这个函数是完成的. 所以你先去反转左子树(函数调用); 再去反转右子树, 因为我们假设这个函数是已经完成了的. 那么左右子树都是交换了的, 那么只用交换左右子树的位置.

这里, 也可以先交换左右子树的位置, 再去反转左右子树. 顺序没关系.