二叉树的遍历

       从大的分类来说有两种遍历方式，一种是深度优先遍历，一种是广度优先遍历；比较常用的额就是深度优先遍历的递归法

   因为这一次练习主要是对递归法的使用，总结以递归为主

       对二叉树的三种递归法的掌握是后面练习的关键，就是是对数组的遍历一样，怎么遍历是一回事，怎么根据题意对节点进行处理时另外一回事

题目总结

简单遍历

144.二叉树的前序遍历

145.二叉树的后序遍历

94.二叉树的中序遍历

226.翻转二叉树

101.对称二叉树

是不是对称二叉树就是检测根节点的左右子树是不是互为翻转二叉树

深度和高度

• 104.二叉树的最大深度
  
• 559.n叉树的最大深度
  
• 111.二叉树的最小深度
  

常见二叉树

• 222.完全二叉树的节点个数
  
• 110.平衡二叉树
  

递归技巧

• 404.左叶子之和

• 怎么判断左叶子是关键
  

• 513.找树左下角的值

• 一次遍历做两件事
  

回溯思想

• 257.二叉树的所有路径
  
• 112.路径总和
  
• 113.路径总和||  
  

构造二叉树

106. 从中序与后序遍历序列构造二叉树 105.从前序与中序遍历序列构造二叉树

中序遍历得到的数组不能准确获取到根节点

从前序遍历数组和后序遍历数组中可以准确得到根节点

• 654.最大二叉树
  
• 617.合并二叉树

• 同时遍历两个二叉树，然后对其节点进行操作
• 可以创建一个新的树，也可以直接在其中一棵树上进行操作

二叉搜索树

做不出来的时候将二叉搜索树看作有序数组进行处理

• 700.二叉搜索树中的搜索
• 98.验证二叉搜索树

双指针法

       将二叉搜索树看作有序数组来对待

• 530.二叉搜索树的最小绝对值
• 501.二叉搜索树的众数
• 538.把二叉树转换成累加树

找节点公共祖先

• 236.二叉树的最近公共祖先
• 235.二叉搜索树的最近公共祖先

增删操作

• 701.二叉搜索树的插入操作

• 没有难度

450.删除二叉搜索树中的节点

删除一个节点，要分析清楚删除节点的不同情况

因为只删除一个节点，找到这个值的时候就是删除节点和返回的时候

所以删除节点的操作就在终止条件中

669.修剪二叉搜索树

根据特性进行删除会更加轻松

因为要保留的是一个区间，所以大于和小于区间的子树都可以直接略去

实际上就是找到小于左区间的节点，将其和其的左子树去掉

再将大于右区间的节点找到，将其和其的右子树去掉

构建二叉搜索树

• 108.将有序数组转换成二叉搜索树

• 跟前、中序和后、中序数组构造二叉树的思路比较像

心得感悟

往往觉得二叉树的题目比较难做的原因是因为对二叉树的遍历不熟悉，对递归不熟悉

其次就是不能根据题目的表意看透题目想考察的内容，比如求二叉树的最大深度其实求树的高度就可以

根据二叉树的特性做题会更简单

递归的终止条件一定要分析清楚情况

选对遍历方式是成功的第一步

遍历过程中的逻辑处理也是比较难以驾驭的，在写代码的时候，站在不同节点的角度时思考起来更轻松