1. 二叉树找值为x的节点

代码实现分析

代码步骤分析：

1. 判断根节点是不是空，是空就返回NULL

2. 不是NULL，就判断该节点的数据是不是要找的数据，是 —>（找到了，一层一层返回上去）

3. 不是要找的数据，就开始调用左子树（如果左子树一直没找到），从最后递归到的NULL开始返回，返回到调用的地方，然后开始调用最后一层的右子树,如果左子树和右子树都递归完了，还没找到就返回NULL

4. 如果一颗二叉树左子树和右子树都有要找的值，只要先找到其中一个，该值就会被一层一层的返回上去，剩下相同的值就不会找找了

代码实现

// 二叉树查找值为x的结点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
    return NULL;
  if (root->data == x)
    return root;
  BTNode* ret1 = TreeFind(root->left, x);
  if (ret1)
    return ret1;
  BTNode* ret2 = TreeFind(root->right, x);
  if (ret2)
    return ret2;
  return NULL;
}

递归展开图

举例：假设我们这里找5这个节点

注意：我这里把5的位置换了下，让他在左子树就可以被找到（还是画出的左子树的递归图）

过程讲解：1. 一直递归调用左边，递归到3的左儿子是NULL，返回到调用NULL的地方，开                          始调用3的右儿子，发现也是NULL

                 2. 这时返回到调用3的地方，3是被2的左边调用的，返回后，开始递归2的右儿子

                 3. 这时要找的数据x和data相同，if条件符合，执行return，然后就开始返回上去

                 4. 首先返回到2调用右儿子的地方，if语句为真，继续返回，返回到2被1调用的地                        方

                 5. 还是if条件为真，返回出去了，这时整个递归就结束了

2. 求二叉树层数

代码思路分析

代码实现分析：

1. 先判断根节点是不是为空，为空就返回NULL，就结束了

2. 走到这里那根节点就不是空，不是空就开始一直递归树的左边，递归到3的左儿子，左儿子是空，这时if条件判断成立，就返回0，开始递归3的右儿子，右儿子也为NULL，这时左返回的层数和右返回的层数比较，由于左边和右边一样都为0，那就随便返回一个+1

3. 节点3的左右儿子都返回完了，这时开始递归调用2的右子树，右子树为空，和3返回的作比较，3返回的值大，那就返回层数2

4. 后面和3的逻辑差不多，最后就是比较节点2返回的层数和4返回的层数谁大，然会就返回给1，节点1再+1，然会就返回出去，结束整个递归

通过上面的分析可以看出，这个是二叉树遍历顺序中的后序遍历

代码实现

int TreeDepth(BTNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  int leftDepth = TreeDepth(root->left);
  int rightDepth = TreeDepth(root->right);
  return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

3. 二叉树的销毁

代码思路分析

前中后序遍历，哪个更适合这里的二叉树销毁呢？

如果采用前序遍历去销毁，一进来就销毁根节点，节点中存着的左孩子和右孩子的指针，如果我们一进来就销毁根节点，这时的左右孩子指针就也被销毁了，不能遍历下去了

中序遍历也一样

后序遍历访问根的顺序——左子树—>右子树—>根，所以我们使用后序遍历可以轻松的避免上面的问题发生

代码实现

通过上面可以知道是后续遍历，代码步骤分析如下

1. 还是一开始就递归调用左边，递归到NULL就返回，开始递归调用右边，右边到NULL，然      后就释放节点，这时就回到2，先不销毁2，先递归2的右边，是NULL，然后就销毁节点2

2. 节点2销毁后，就返回1的右边，开始递归调用1的右孩子》》》（原理和左边相同）

void TreeDestroy(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  TreeDestroy(root->left);
  TreeDestroy(root->right);
  free(root);
}

运行结果

注意点：一般递归不好调试，我们可以借助打印，来理解

由于我们使用的是后序遍历，所以我们这里打印的销毁节点的顺序，就是后序遍历的顺序

4. 二叉树的一些OJ题目

下面是一些Leetcode上的一些二叉树练习题，价值还是蛮高的，可以点击OJ链接跳转去做题

后面小余也会出这些题目的题解和做题心得，大家可以关注下哦！

1. 单值二叉树                      OJ链接跳转

2. 检查两颗树是否相同       OJ链接跳转

3. 对称二叉树                      OJ链接跳转

4. 二叉树的前序遍历           OJ链接跳转

5. 二叉树中序遍历              OJ链接跳转

6. 二叉树的后序遍历           OJ链接跳转

7. 另一颗树的子树              OJ链接跳转

如果觉得文章不错，期待你的一键三连哦，你个鼓励是我创作的动力之源，让我们一起加油，顶峰相见！！！