这有位大哥，执意让先刷二叉树，培养所谓的框架思维，其实，我刚刚刷完100道题，正在总结题目，觉得也无可厚非：在做一些动态规划的题目时，确实也感受到了，再说这是一种常见的思维，需要特意训练一下：
https://labuladong.github.io/algo/2/20/33/

https://www.yuque.com/wangtengyun/vwapnv/vxe7ay

前序遍历：

1448. 统计二叉树中好节点的数目

  1. var goodNodes = function(root) {
  2.     let count = 0;
  4.     function dfs(node, preMax) {
  5.         if (!node) {
  6.             return;
  7.         }
  9.         if (node.val >= preMax) { // 先判断是先序的操作
  10.             count++;
  11.             preMax = node.val;
  12.         }
  14.         dfs(node.left, preMax);
  15.         dfs(node.right, preMax);
  16.     }
  18.     dfs(root, -Infinity);
  20.     return count;
  21. };

带着深度depth 的 dfs

104. 二叉树的最大深度

  1. var maxDepth = function(root) {
  2.     let maxDepth = 0;
  3.     function traverse(node, depth) { // depth 是 node 所在 深度，初始为0
  4.         if (node === null) {
  5.             if (maxDepth < depth) {
  6.                 maxDepth = depth;
  7.             }
  8.             return;
  9.         }
  11.         traverse(node.left, depth + 1);
  12.         traverse(node.right, depth + 1);
  13.     }
  15.     traverse(root, 0);
  17.     return maxDepth;
  18. };

199. 二叉树的右视图

下面的解法是错的，但是想强调的一点是: 技法的熟练，下面解法思路是 1）先只递归最右边的一只 2）然后再找树的最大深度。两者合并就是答案。但是在1）中最右边的不一定就是右视图的上半部分。 所以还是要使用层遍历的手段。

  1. /**
  2.  * Definition for a binary tree node.
  3.  * function TreeNode(val, left, right) {
  4.  *     this.val = (val===undefined ? 0 : val)
  5.  *     this.left = (left===undefined ? null : left)
  6.  *     this.right = (right===undefined ? null : right)
  7.  * }
  8.  */
  9. /**
  10.  * @param {TreeNode} root
  11.  * @return {number[]}
  12.  */
  13. var rightSideView = function(root) {
  14.     let ans = [];
  16.     let maxRightDepth = 0;
  17.     function dfsRight(node, depth) {
  18.         if (!node) {
  19.             maxRightDepth = depth;
  20.             return;
  21.         }
  23.         ans.push(node.val); // 前序 or 中序？
  24.         dfsRight(node.right, depth + 1);
  25.     }
  27.     dfsRight(root, 0);
  29.     let maxDepth = 0;
  30.     let maxDepthPath = [];
  31.     function dfs(node, path) {
  32.         if (!node) {
  33.             return;
  34.         }
  36.         path.push(node); // 记录本节点
  38.         if (maxDepth < path.length) {
  39.             maxDepth = path.length;
  40.             maxDepthPath = path;
  41.         }
  43.         dfs(node.left, [...path]);
  44.         dfs(node.right, [...path]);
  45.     }
  47.     dfs(root, []);
  49.     if (maxRightDepth < maxDepth) {
  50.         let tmp = maxDepthPath.slice(maxRightDepth).map(n => n.val);
  51.         return [...ans, ...tmp];
  52.     }
  54.     return ans;
  55. };

层序遍历轻松解决：
这几天写dfs多了，好的方法考虑少了。

  1. var rightSideView = function(root) {
  2.     if (!root) {
  3.         return [];
  4.     }
  5.     let ans = [];
  6.     let queue = [root];
  8.     while (queue.length > 0) {
  9.         let size = queue.length;
  10.         ans.push(queue[size - 1].val);
  12.         for (let i = 0; i < size; i++) {
  13.             let cur = queue.shift();
  14.             cur.left && queue.push(cur.left);
  15.             cur.right && queue.push(cur.right);
  16.         }
  17.     }
  19.     return ans;
  20. };

543. 二叉树的直径

不是遍历树的思路，而是递归分解问题的思路

  1. var diameterOfBinaryTree = function(root) {
  2.     if (root === null) {
  3.         return 0;
  4.     }
  6.     let max = 0;
  8.     function getMaxDepth (node) {
  9.         if (node === null) {
  10.             return 0;
  11.         }
  12.         let leftDepth = getMaxDepth(node.left);
  13.         let rightDepth = getMaxDepth(node.right);
  14.         if (max < (leftDepth + rightDepth + 1)) {
  15.             max = leftDepth + rightDepth + 1;
  16.         }
  17.         return Math.max(leftDepth, rightDepth) + 1;
  18.     }
  20.     getMaxDepth(root);
  22.     return max - 1;
  23. };

100. 相同的树

同时遍历两颗树，和使用下标同时遍历两个数组时一样的。

  1. var isSameTree = function(p, q) {
  2.     let isDifferent = false;
  4.     function walk(node_1, node_2) {
  5.         if (isDifferent) {
  6.             return;
  7.         }
  9.         if (node_1 === null && node_2 === null) {
  10.             return;
  11.         }
  13.         if (node_1 && node_2 && (node_1.val === node_2.val)) {
  14.             walk(node_1.left, node_2.left);
  15.             walk(node_1.right, node_2.right);
  16.         } else {
  17.             isDifferent = true;
  18.             return; 
  19.         }
  21.         walk(node_1.left, node_2.left);
  22.         walk(node_1.right, node_2.right);
  23.     }
  25.     walk(p, q);
  27.     return !isDifferent;
  28. };

101. 对称二叉树

企图前序遍历左子树 和 后续遍历右子树 完成对称的检查

  1. var isSymmetric = function(root) {
  2.     if (root === null) return true;
  4.     const preArray = [];
  5.     function pre(node) {
  6.         if (node === null) {
  7.             return;
  8.         }
  10.         preArray.push(node.val);
  11.         pre(node.left);
  12.         pre(node.right);
  13.     }
  14.     pre(root.left);
  16.     const postArray = [];
  17.     function post(node) {
  18.         if (node === null) {
  19.             return;
  20.         }
  22.         // post(node.left);
  23.         // post(node.right);
  25.         // 交换顺序，就是逆序了！！
  26.         post(node.right);
  27.         post(node.left);
  29.         postArray.push(node.val);
  30.     }
  31.     post(root.left);
  33.     if (preArray.length !== postArray.length) {
  34.         return false;
  35.     }
  37.     let n = preArray.length;
  38.     for (let i = 0; i < Math.floor(n / 2) + 1; i++) {
  39.         if (preArray[i] !== postArray[n - i - 1]) {
  40.             return false;
  41.         }
  42.     }
  44.     return true;
  45. };

这样的解过不去：
image.png
如同 100 的思路，去同时遍历两颗（子）树：

  1. var isSymmetric = function(root) {
  2.     if (root === null) return true;
  4.     let isSame = true;
  5.     function walk(node_1, node_2) {
  6.         if (!isSame) {
  7.             return;
  8.         }
  10.         if (node_1 === null && node_2 === null) {
  11.             return;
  12.         }
  14.         if (node_1 && node_2 && (node_1.val === node_2.val)) {            
  15.             walk(node_1.left, node_2.right);
  16.             walk(node_1.right, node_2.left);
  17.         } else {
  18.             isSame = false;
  19.             return;
  20.         }
  21.     }
  23.     walk(root.left, root.right);
  25.     return isSame;
  26. };

226. 翻转二叉树

遍历思路：找到每个节点要做什么 和 以及什么时机做（前序 中序 后序）

  1. var invertTree = function(root) {
  2.     function walk(node) {
  3.         if (!node) {
  4.             return;
  5.         }
  6.         let tmp = node.left;
  7.         node.left = node.right;
  8.         node.right = tmp;
  10.         walk(node.left);
  11.         walk(node.right);
  12.     }
  14.     walk(root);
  16.     return root;
  17. };

划分小问题：

  1. var invertTree = function(root) {
  2.     function _invertTree(node) {
  3.         if (node === null) {
  4.             return null; // 终止条件而非返回
  5.         }
  7.         // node.left 被先后改变，影响了结果
  8.         // node.left = _invertTree(node.right);
  9.         // node.right = _invertTree(node.left);
  11.         let left = _invertTree(node.right); // 先存下，后赋值
  12.         let right = _invertTree(node.left);
  14.         node.left = left;
  15.         node.right = right;
  17.         return node;
  18.     }
  20.     return _invertTree(root);
  21. };

116. 填充每个节点的下一个右侧节点指针

1）利用 层遍历的套路：

  1. var connect = function(root) {
  2.     if (root === null) {
  3.         return null;
  4.     }
  5.     const queue = [];
  6.     queue.push(root);
  8.     while (queue.length) {
  9.         let preNode = null;
  10.         let size = queue.length;
  11.         for (let i = 0; i < size; i++) {
  12.             let curNode = queue.shift();
  14.             curNode.left && queue.push(curNode.left);
  15.             curNode.right && queue.push(curNode.right);
  17.             if (preNode) {
  18.                 preNode.next = curNode;
  19.             }
  20.             preNode = curNode;
  21.         }
  22.         preNode.next = null;
  23.     }
  25.     return root;
  26. };

但是还有更明确的遍历套路：

  1. // 也是好方法：以下写法层遍历更明确！！！
  2. var connect = function(root) {
  3.     if (!root) return null;
  4.     let queue = [root];
  5.     while(queue.length) {
  6.         const nums = queue.length;
  7.         for(let i = 0; i < nums; i++) {
  8.             let node = queue.shift();
  9.             node.left && queue.push(node.left);
  10.             node.right && queue.push(node.right);
  11.         }
  12.         for(let i = 0; i< queue.length - 1; i++) { // 多么明确
  13.             queue[i].next = queue[i+1];
  14.         }
  15.     }
  16.     return root;
  17. };

2）很另类，我觉得我学不会
https://labuladong.github.io/algo/2/20/34/
image.png

二叉树路径

236. 二叉树的最近公共祖先

这道题的遍历过程很简单，代码也简单。关键是要抓住题目的限制条件：
image.png
所以有很多推测，对于一个 node如果一个子树 node.left 没有 p 或 q，而另一个子树 node.right 只检测出来有 p 或 q 那么可以说，结果一定在 node.left。

  1. var lowestCommonAncestor = function(root, p, q) {
  3.     function walk(node) { // 找到 p 或 q，直接返回
  4.         if (node === null || node.val == p.val || node.val === q.val) {
  5.             return node;
  6.         }
  8.         let left = walk(node.left);
  9.         let right = walk(node.right);
  11.         if (left && right) {
  12.             return node;
  13.         } 
  16.         // else if (left && !right) {
  17.         //     return left;
  18.         // } else if (!left && right) {
  19.         //     return right;
  20.         // } else {
  21.         //     return null;
  22.         // }
  24.         return left || right;
  25.     }
  27.     return walk(root);
  28. };
  30. // Tree 相关代码在后面
  31. const root = new Tree([3,5,1,6,2,0,8,null,null,7,4]);
  32. const p = new TreeNode(5);
  33. const q = new TreeNode(1);
  34. lowestCommonAncestor(root, p, q);

235. 二叉搜索树的最近公共祖先 （235 和 236 是一样的题目）

  1. var lowestCommonAncestor = function(root, p, q) {
  2.     function walk(node) {
  3.         if (!node) {
  4.             return;
  5.         }
  7.         if ([p.val, q.val].includes(node.val)) {
  8.             return node;
  9.         }
  11.         // 在 walk 上加条件判断
  12.         let left;
  13.         let right;
  14.         if (p.val <= node.val && q.val <= node.val) {
  15.             left = walk(node.left);
  16.         } else if (p.val <= node.val && q.val >= node.val || q.val <= node.val && p.val >= node.val) {
  17.             left = walk(node.left);
  18.             right = walk(node.right);
  19.         } else if (p.val >= node.val && q.val >= node.val) {
  20.             right = walk(node.right);
  21.         }
  23.         if (left && right) {
  24.             return node;
  25.         }
  27.         return left || right;
  28.     }
  30.     return walk(root);
  31. };

1650. 二叉树的最近公共祖先 III

题目一开始想当然了。题目并没有给出 树的 root ，只给出两个节点而已。
思路也比较简单：节点通过 parent 能找到继承链。
1）先找到一个节点的完整继承链，
2）然后再一步一步找 另一个节点 继承链：每个都比较是否已经出现在另一个节点的继承链中，有就是公共节点。
注意，继承链一开始要把自己包括进去。

  1. var lowestCommonAncestor = function(p, q) {
  2.     let visitedOfp = new Set();
  3.     while (p) { // 有值才加入
  4.         visitedOfp.add(p);
  5.         p = p.parent;
  6.     }
  8.     while(q) {
  9.         if (visitedOfp.has(q)) {
  10.             return q;
  11.         }
  12.         q = q.parent;
  13.     }
  15.     return null;
  16. };

124. 二叉树中的最大路径和

我这个是传统的递归写法，但不是遍历二叉树的标准姿势。
这次我们递归的返回 和 题目要求有关，题目要找最大路径和，那我们就返回某个节点的最大路径。

  1. var maxPathSum = function(root) {
  2.     // let max = 0;
  3.     let max = root.val;
  5.     function walk(node) { // 递归返回的是，包含 node 节点的 “串”。注意：这个串需要和父节点去组成大串！
  6.         if (!node) {
  7.             // return 0;
  8.             return -Infinity; // 不想让别人算到这一支
  9.         }
  11.         if (!node.left && !node.right) {
  12.             return node.val;
  13.         }
  15.         let leftSum = walk(node.left);
  16.         let rightSum = walk(node.right);
  18.         let _max = Math.max(node.val, leftSum + node.val, rightSum + node.val); // 带有父节点的最大值
  20.         let sum = node.val + leftSum + rightSum;
  21.         max = Math.max(max, _max, sum, leftSum, rightSum); // 和 不带父节点的最大值 比较
  23.         return _max; // _max 代表的是递归体系
  24.     }
  26.     walk(root);
  28.     return max;
  29. }

112. 路径总和

比 124 简单多了，平时写叶子节点 dfs 的边界处理（有时直接忽略），不需要在遍历过程中使用map记录值，二叉的树遍历，只要前序遍历就可以。我现在对二叉树的理解也慢慢牛逼了。

  1. var hasPathSum = function(root, targetSum) {
  2.     if (!root) {
  3.         return false;
  4.     }
  6.     let has = false;
  7.     function dfs(node, parentVal) {
  8.         if (!node) { // 这里不能完全判断 parent 是叶子节点
  9.             return;
  10.         }
  11.         if (has) { // 优化！！！
  12.             return;
  13.         }
  14.         if (!node.left && !node.right) { // 当前是叶子节点
  15.             if (parentVal + node.val === targetSum) {
  16.                 has = true;
  17.             }
  18.         }
  20.         dfs(node.left, parentVal + node.val);
  21.         dfs(node.right, parentVal + node.val);
  22.     }
  24.     dfs(root, 0);
  26.     return has;
  27. };

体验递归：

剑指 Offer 27. 二叉树的镜像

  1. var mirrorTree = function(root) {
  2.     if (!root) { // 边界条件1
  3.         return root;
  4.     }
  5.     if (!root.left && !root.right) { // 边界条件2
  6.         return root;
  7.     }
  9.     let right = mirrorTree(root.left);
  10.     let left = mirrorTree(root.right);
  11.     root.left = left;
  12.     root.right = right;
  14.     return root;
  15. };

使用递归去试错

递归使用的天花板：使用递归去试错

951. 翻转等价二叉树

  1. var flipEquiv = function(root1, root2) {
  2.     if (root1 && root2 && root1.val === root2.val) {
  3.         return (flipEquiv(root1.left, root2.left) && flipEquiv(root1.right, root2.right))
  4.                 || (flipEquiv(root1.left, root2.right) && flipEquiv(root1.right, root2.left));
  5.     }
  6.     if (root1 === root2) { // root1 root2 都是 null
  7.         return true;
  8.     }
  9.     return false;
  10. }

572. 另一棵树的子树

和 951 一样，是用递归去试错的思想

  1. var isSubtree = function(root, subRoot) {
  2.     if (root === null && subRoot === null) {
  3.         return true;
  4.     }
  5.     if (!(root && subRoot)) {
  6.         return false;
  7.     }
  8.     if (!root.left && !root.right && !subRoot.left && !subRoot.right && root.val === subRoot.val) {
  9.         return true;
  10.     }
  12.     // 后面的是 root 和 subRoot 同时存在
  13.     if (root.val !== subRoot.val) {
  14.         return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)
  15.     }
  16.     if (isSameTree(root.left, subRoot.left) && isSameTree(root.right, subRoot.right)) {
  17.         return true;
  18.     }
  19.     return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
  20. };
  22. function isSameTree(root1, root2) {
  23.     if (!root1 && !root2) {
  24.         return true;
  25.     }
  26.     if (root1 && root2 && root1.val === root2.val) {
  27.         return isSameTree(root1.left, root2.left) && isSameTree(root1.right, root2.right);
  28.     }
  29.     return false;
  30. }

114. 二叉树展开为链表

分解为子问题去解决：细节是魔鬼

  1. var flatten = function(root) {
  2.     function _flatten(node) {
  3.         if (node === null) {
  4.             return [null, null];
  5.         }
  6.         if (!node.left && !node.right) {
  7.             return [node, node];
  8.         }
  9.         const [leftHead, leftTail] = _flatten(node.left);
  10.         const [rightHead, rightTail] = _flatten(node.right);
  12.         let _head = null;
  13.         let _tail = null;
  15.         if (leftTail) { // 连接两个串
  16.             leftTail.right = rightHead;
  17.         }
  19.         _head = leftHead || rightHead;
  20.         _tail = rightTail || leftTail; // 细节要注意了
  22.         node.right = _head;
  23.         node.left = null;
  25.         return [node, _tail];
  26.     }
  28.     _flatten(root);
  29.     return root;
  30. };

25. K 个一组翻转链表

和 114. 二叉树展开为链表 类似的题目。

生成树：

654. 最大二叉树

看看思路解析，就能轻易地想到拆分子问题 递归的方法

  1. var constructMaximumBinaryTree = function(nums) {
  2.     if (nums.length === 0) {
  3.         return null;
  4.     }
  5.     if (nums.length === 1) {
  6.         return new TreeNode(nums[0]);
  7.     }
  9.     let max = -Infinity;
  10.     let maxIndex = null;
  11.     for (let i = 0; i < nums.length; i++) {
  12.         let cur = nums[i];
  13.         if (max < cur) {
  14.             max = cur;
  15.             maxIndex = i;
  16.         }
  17.     }
  19.     let node = new TreeNode(max);
  20.     node.left = constructMaximumBinaryTree(nums.slice(0, maxIndex));
  21.     node.right = constructMaximumBinaryTree(nums.slice(maxIndex + 1));
  23.     return node;
  24. };

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

和 654 一样拆分子问题

  1. var buildTree = function(preorder, inorder) {
  2.     if (preorder.length === 1 && inorder.length === 1) {
  3.         return new TreeNode(preorder[0]);
  4.     }
  5.     if (preorder.length === 0 && inorder.length === 0) {
  6.         return null;
  7.     }
  9.     const rootValue = preorder[0];
  10.     const rootValueIndex = inorder.indexOf(rootValue);
  12.     const root = new TreeNode(rootValue);
  13.     root.left = buildTree(preorder.slice(1, rootValueIndex + 1), inorder.slice(0, rootValueIndex));
  14.     root.right = buildTree(preorder.slice(rootValueIndex + 1), inorder.slice(rootValueIndex + 1));
  16.     return root;
  17. };

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

完全相同的结构去做的

  1. var buildTree = function(inorder, postorder) {
  2.     if (inorder.length === 1 && postorder.length === 1) {
  3.         return new TreeNode(inorder[0]);
  4.     }
  5.     if (inorder.length === 0 && postorder.length === 0) {
  6.         return null;
  7.     }
  9.     const rootValue = postorder[postorder.length - 1];
  10.     const rootValueIndex = inorder.indexOf(rootValue);
  12.     const root = new TreeNode(rootValue);
  13.     root.left = buildTree(inorder.slice(0, rootValueIndex), postorder.slice(0, rootValueIndex));
  14.     root.right = buildTree(inorder.slice(rootValueIndex + 1), postorder.slice(rootValueIndex, postorder.length - 1));
  16.     return root;
  17. };

小结：

生成树的算法：
1）找到子问题，
2）构建边界条件
3）注意子问题的传值

根据二叉树的层遍历结果，反序列化生成树

前序 和 中序，或 中序 和 后序 都能唯一确定树。
层序 单独就可以确定 唯一的树。

  1. function Tree(arr) { // 两个队列，要想实现宽度遍历，必须使用队列。
  2.     let val = arr.shift();
  3.     let root = new TreeNode(val);
  5.     let queue = [];
  6.     queue.push(root);
  8.     while (queue.length) {
  9.         const cur = queue.shift();
  11.         if (arr.length > 0) {
  12.             let leftVal = arr.shift();
  13.             if (leftVal !== null) {
  14.                 let leftNode = new TreeNode(leftVal);
  15.                 cur.left = leftNode;
  16.                 queue.push(leftNode);
  17.             }
  18.         } else {
  19.             break;
  20.         }
  22.         if (arr.length > 0) {
  23.             let rightVal = arr.shift();
  24.             if (rightVal !== null) {
  25.                 let rightNode = new TreeNode(rightVal);
  26.                 cur.right = rightNode;
  27.                 queue.push(rightNode);
  28.             }
  29.         } else {
  30.             break;
  31.         }
  32.     }
  34.     return root;
  35. }

297. 二叉树的序列化与反序列化

  1. var serialize = function(root) {
  2.     // 先序遍历输出
  3.     function pre(node) {
  4.         if (!node) {
  5.             return 'None'; // 也不知是什么狗屁
  6.         }
  8.         let leftStr = pre(node.left);
  9.         let rightStr = pre(node.right);
  10.         return node.val + ',' + leftStr + ',' + rightStr;
  11.     }
  13.     return pre(root);
  14. };
  16. /**
  17.  * Decodes your encoded data to tree.
  18.  *
  19.  * @param {string} data
  20.  * @return {TreeNode}
  21.  */
  22. var deserialize = function(data) { // 这个反序列化 的递归很有思思，可谓是经典吧
  23.     const list = data.split(',');
  25.     function dfs(list) {
  26.         let cur = list.shift();
  27.         if (cur === 'None') {
  28.             return null;
  29.         }
  31.         let newNode = new TreeNode(cur);
  32.         newNode.left = dfs(list);
  33.         newNode.right = dfs(list);
  35.         return newNode;
  36.     }
  38.     return dfs(list);
  39. };

层序遍历的模板

专门讲后序

为什么专门讲后序？感觉不凡呢。
image.png
后序 去解决“子树”问题。

652. 寻找重复的子树

不算什么高见：
https://mp.weixin.qq.com/s/LJbpo49qppIeRs-FbgjsSQ
自己写一版吧，练练手：

  1. var findDuplicateSubtrees = function(root) {
  2.     let result = [];
  3.     let map = new Map(); // key: 子树遍历的后序结果字符串，value 为 子树的根节点, value 改为 次数
  4.     function walk(node) {
  5.         if (node === null) {
  6.             return 'none';
  7.         }
  9.         let leftVal = walk(node.left);
  10.         let rightVal = walk(node.right);
  11.         let key = `${leftVal},${rightVal},${node.val}`;
  13.         if (map.has(key)) {
  14.             if (map.get(key) === 1) { // 只想记录第二次 相同的 key，第三次不记录了
  15.                 result.push(node); 
  16.             }
  17.             map.set(key, map.get(key) + 1)
  18.         } else {
  19.             map.set(key, 1);
  20.         }
  22.         return key;
  23.     }
  25.     walk(root);
  27.     return result;
  28. };

很容易就写出来了，后序 在 写 子树 确实简单很多。

归并排序其实后序遍历

逻辑阐述能力，也非常重要。所以要讲清楚自己的思考过程。