二叉树的前序：中左右
二叉树的中序：左中右
二叉树的后序：左右中
题型一：

合并二叉树

image.png
思路：同时遍历两棵树相同的结点，即使其中一棵树该结点为null，将他们相加后覆盖某棵树的该结点。利用递归表达更清楚。涉及到BFS和DFS算法。

  1. var mergeTrees = function(root1, root2) {
  2.     if(root1 == null)return root2;
  3.       if(root2 == null)return root1;
  5.       root1.val += root2.val;
  6.       root1.left = mergeTrees(root1.left,root2.left);
  7.       root1.right = mergeTrees(root1.right,root2.right);
  8.         return root1;
  9. };//深度

题型二：
二叉树的遍历：

二叉树的前序遍历

二叉树的中序遍历

二叉树的后序遍历

思路：递归遍历

  1. var preorderTraversal = function(root) {
  2.     var out = [];
  3.     function getVal(tree) {
  4.         if(tree == null)return;
  5.         else out.push(tree.val);//中
  6.         getVal(tree.left);//左
  7.         getVal(tree.right);//右
  8.       //根据前中后序来变换位置。
  9.       前：中左右
  10.       中：左中右
  11.       后：左右中
  12.     }
  13.     getVal(root);
  14.     return out;
  15. };

题型三：

二叉树的最大深度

image.png
思路：递归调用，边界条件是该结点为null

  1. var maxDepth = function(root){
  2.     return root==null?0:Math.max(maxDepth(root.left),maxDepth(root.right))+1;
  3. }

题型四：

翻转二叉树

image.png
image.png
（这段简直太草了）
思路：递归

  1. var invertTree = function(root) {
  2.     if(root == null)
  3.     return null;
  4.     const left = invertTree(root.left);
  5.     const right = invertTree(root.right);
  6.     root.right = left;
  7.     root.left = right;
  8.     return root;
  9. };

题型五：

对称二叉树

思路：递归，判断一个树是否对称，看左右子树是否相同，然后判断左右子树的右左子树是否相同。

  1. var isSymmetric = function(root) {
  2.     function check(a,b){
  3.         if(a==null&&b==null)return true;
  4.         else if(a==null||b==null)return false;
  5.         else return a.val==b.val && check(a.left,b.right) && check(a.right,b.left);
  6.     }
  7.     return check(root,root);
  8. };

题型六：

路径总和

思路：递归，判断是否是叶子结点，是的话就看值符不符合，不是叶子结点就拿和减去当前结点数值来递归

  1. const hasPathSum = (root, sum) => {
  2.   if(root == null)return false;
  3.   if(root.left==null&&root.right==null){
  4.       return sum - root.val == 0;
  5.   }
  6.   else return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
  7. }

题型七：

两数之和 IV - 输入 BST

思路：该题二叉树默认是搜索二叉树，即为左边的子节点小于根节点，右边的子节点大于根节点，这样的中序排下来是一个升序数组，然后用双指针指向头尾来查找答案。

  1. var findTarget = function(root, k) {
  2.     var out = [];
  3.     function seek(tree){
  4.         if(!tree){
  5.             return ;
  6.         }
  7.         seek(tree.left);
  8.         out.push(tree.val);
  9.         seek(tree.right);
  10.     }
  11.     seek(root);
  12.     let head = 0;
  13.     let tail =out.length-1;
  14.     while(head<tail){
  15.         if(out[head]+out[tail] == k)return true;
  16.         else if(out[head]+out[tail]<k){
  17.             head++
  18.         }
  19.         else tail--;
  20.     }
  21.     return false;
  22. };

题型八：

二叉搜索树的最近公共祖先

思路：当此结点都大于pq时，说明祖先结点在左子树；都小于时，说明在右子树。一旦一大一小或者有个相等时，说明此时的结点即为祖先节点。

  1. var lowestCommonAncestor = function(root, p, q) {
  3.     while(true){
  4.         if(root.val>p.val&&root.val>q.val){
  5.             root = root.left;
  6.         }
  7.         else if(root.val<p.val&&root.val<q.val){
  8.             root = root.right;
  9.         }
  10.         else{
  11.             break;
  12.         }
  13.     }
  14.     return root;
  15. };

或者：两次遍历，得到去两个结点的路径，记录在数组中，然后寻找两个数组相同的路径，直到不同为止最大的索引即为祖先结点所在位置。
题型九：

二叉树的层序遍历

思路：用一个数组从根节点开始记录，初始时数组仅有根节点，此时将目的数组开放[0]，将根节点从记录数组移动到目的数组，并检查是否有子节点，有的话将子节点移动到记录数组，将子节点当做根节点循环此步骤直到没有子节点放入记录结点。

  1. var levelOrder = function(root) {
  2.     const ret = [];
  3.     if (!root) {
  4.         return ret;
  5.     }
  7.     const q = [];
  8.     q.push(root);
  9.     while (q.length !== 0) {
  10.         const currentLevelSize = q.length;
  11.         ret.push([]);
  12.         for (let i = 1; i <= currentLevelSize; ++i) {
  13.             const node = q.shift();
  14.             ret[ret.length - 1].push(node.val);
  15.             if (node.left) q.push(node.left);
  16.             if (node.right) q.push(node.right);
  17.         }
  18.     }
  20.     return ret;
  21. };

题型十：

剑指 Offer 32 - I. 从上到下打印二叉树

思路：
广度优先算法，用队列先进先出的性质，先将根节点放入队列，将根节点数据放入目标数组，然后监测左右节点并放入队列，重复以下步骤。因为先进先出，这样会根据从上到下的顺序进出。

  1. const levelOrder = root => {
  2.     if (!root) return [];
  3.     // 创建队列，并将根节点入队
  4.     const queue = [root];
  5.     const res = [];
  6.     while (queue.length) {
  7.         // 获取根节点，根节点出队
  8.         const n = queue.shift();
  9.         // 访问队头
  10.         res.push(n.val);
  11.         // 队头的子节点依次入队
  12.         n.left && queue.push(n.left);
  13.         n.right && queue.push(n.right);
  14.     }
  15.     return res;
  16. };

题型十一：

剑指 Offer 28. 对称的二叉树

思路：
递归

  1. var isSymmetric = function(root) {
  2.     function judge(left,right){
  3.         if(left == null&&right == null)return true;
  4.         if(left == null||right == null||left.val != right.val) return false;
  5.         return judge(left.left,right.right)&&judge(left.right,right.left);
  6.     }
  7.     return root==null?true:judge(root.left,root.right);
  8. };