理解和默写 二叉树的基本操作
树的操作基本和递归密不可分。一般主要考察二叉树的操作。
所以这里简单的归纳总结下，二叉树的基本操作。
像熟练基本战斗技能一样，这样虐杀敌人才得心应手~
什么是二叉树
二叉树（Binary Tree）：每个结点都有且只有两个子节点，其中子节点可以为空节点。
// 前端用类表示 function TreeNode(val) { this.val = val; this.left = this.right = null; }
二叉树的前中后序遍历：递归法
二叉树的三种遍历：前、中、后序遍历，是以根节点出现的位置作为前中后的。
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
网络异常，图片无法展示
|
递归写法，超简单，三种遍历可以一起来：
function traverse(tree){ if(!tree){ return [] } let res = [] // 这行代码的位置决定了 前中后序遍历，此处是前，放下面一行就是中，放下下面一行就是后 res.push(tree.val) tree.left && traverse(tree.left) tree.right && traverse(tree.right) }
二叉树的前中后序遍历：迭代写法
迭代写法其实稍显麻烦的，也不容易理解，万一不行就掌握递归法~
网络异常，图片无法展示
|
前序遍历：也就是 中左右，中先碰到就先出去，然后左右是反着的，因为是栈
- 将根结点入栈
- 取出栈顶结点，将结点值 push 进结果数组
- 若栈顶结点有右孩子，则将右孩子入栈
- 若栈顶结点有左孩子，则将左孩子入栈
循环二三四步，直到栈空。
function before(tree) { if (!tree) { return []; } let res = []; let stack = [tree]; while (stack.length) { const cur = stack.pop(); res.push(cur.val); cur.right && stack.push(cur.right); cur.left && stack.push(cur.left); } return res; }
后序遍历类似，但是结果数组从前开始插入
function after(tree) { if (!tree) { return []; } let res = []; let stack = [tree]; while (stack.length) { const cur = stack.pop(); // 这里换成unshift res.unshift(cur.val); // 这里两个换顺序了 cur.left && stack.push(cur.left); cur.right && stack.push(cur.right); } return res; }
前序和后序都是先处理根结点，然后处理孩子结点。
中序遍历麻烦点：
中序遍历:
function middle(root) { let res = []; let stack = []; let cur = root; while (cur || stack.length) { while (cur) { stack.push(cur); cur = cur.left; } cur = stack.pop(); res.push(cur.val); cur = cur.right; } return res; }
二叉树的层序遍历
网络异常，图片无法展示
|
层序遍历利用队列，一层层的扫，注意，每一层先进去之后，长度先记录下来：
网络异常，图片无法展示
|
var levelOrder = function (root) { if (!root) { return []; } let res = []; let queue = [root]; while (queue.length) { // 当前层 let curArr = []; const len = queue.length; // 核心：这层的长度是一定的，因为后期queue会变化，所以这里要用for for (let i = 0; i < len; i++) { // 这里要有shift const cur = queue.shift(); curArr.push(cur.val); cur.left && queue.push(cur.left); cur.right && queue.push(cur.right); } res.push(curArr.slice()); } return res; };
二叉树的反转
网络异常，图片无法展示
|
var invertTree = function (root) { if (!root) { return null; } let right = root.right; let left = root.left; root.left = invertTree(right); root.right = invertTree(left); return root; };
什么是二叉搜索树
二叉搜索树（Binary Search Tree）简称 BST，别名比如排序二叉树、二叉查找树等~
树的定义总是以递归的形式出现，二叉搜索树也不例外，它的递归定义如下：
- 是一棵空树
- 是一棵由根结点、左子树、右子树组成的树，同时左子树和右子树都是二叉搜索树，且左子树上所有结点的数据域都小于等于根结点的数据域，右子树上所有结点的数据域都大于等于根结点的数据域。
简单点就是左孩子 <= 根结点 <= 右孩子
二叉搜索树的特性
- 二叉搜索树的中序遍历是有序的
- 二叉搜索树的左子树最大的节点是 左子树的最右边的点
- 二叉搜索树的右子树最小的节点是 右子树的最左边的点
二叉搜索树的查找节点
网络异常，图片无法展示
|
简单的就递归：
function search(root, val) { if (!root) return null; if (root.val === val) return root; if (root.left) return search(root.left, val); if (root.right) return search(root.right, val); }
二叉搜索树的添加节点
网络异常，图片无法展示
|
function add(root, val) { if (!root) return new TreeNode(val); if (root.val === val) return root; if (val < root.val) return add(root.left, val); if (val > root.val) return add(root.right, val); }
二叉搜索树的删除节点
网络异常，图片无法展示
|
想要删除某个结点，首先要找到这个结点。在定位结点后，我们需要考虑以下情况：
- 结点不存在，定位到了空结点。直接返回即可。
- 需要删除的目标结点没有左孩子也没有右孩子——它是一个叶子结点，删掉它不会对其它结点造成任何影响，直接删除即可。
- 需要删除的目标结点存在左子树，那么就去左子树里寻找小于目标结点值的最大结点，用这个结点覆盖掉目标结点
- 需要删除的目标结点存在右子树，那么就去右子树里寻找大于目标结点值的最小结点，用这个结点覆盖掉目标结点
- 需要删除的目标结点既有左子树、又有右子树，这时就有两种做法了：要么取左子树中值最大的结点，要么取右子树中取值最小的结点。两个结点中任取一个覆盖掉目标结点，都可以维持二叉搜索树的数据有序性
最后一种情况图示：
网络异常，图片无法展示
|
var deleteNode = function (root, key) { if (!root) return null; if (root.val === key) { if (!root.left && !root.right) { return null; } if (root.left) { // 左边节点的最右边节点 就是 左边最大的节点 let cur = findMax(root.left); // 覆盖的时候，根节点换值 root.val = cur.val; // 左节点直接执行删除操作 root.left = deleteNode(root.left, cur.val); } // 这里必须是else 和上面的操作互斥 else if (root.right) { // 右边节点的最左边节点 就是 左边最小的节点 let cur = findMin(root.right); root.val = cur.val; root.right = deleteNode(root.right, cur.val); } } key < root.val && (root.left = deleteNode(root.left, key)); key > root.val && (root.right = deleteNode(root.right, key)); return root; }; // 寻找左子树最大值 function findMax(root) { while (root.right) { root = root.right; } return root; } // 寻找右子树的最小值 function findMin(root) { while (root.left) { root = root.left; } return root; }
二叉搜索树的判断
网络异常，图片无法展示
|
空树的判定比较简单，关键在于非空树的判定：需要递归地对非空树中的左右子树进行遍历，检验每棵子树中是否都满足 左 < 根 < 右 这样的关系（注意题中声明了不需要考虑相等情况）。
var isValidBST = function (root) { function dfs(root, min, max) { if (!root) { return true; } if (root.val <= min || root.val >= max) { return false; } return dfs(root.left, min, root.val) && dfs(root.right, root.val, max); } return dfs(root, -Infinity, Infinity); };
用有序数组构建二叉搜索树
网络异常，图片无法展示
|
有序的数组从中间拧出来根节点即可，然后就是递归。
var sortedArrayToBST = function (nums) { if (!nums.length) { return null; } const middle = Math.floor(nums.length / 2); let root = new TreeNode(nums[middle]); root.left = sortedArrayToBST(nums.slice(0, middle)); root.right = sortedArrayToBST(nums.slice(middle + 1)); return root; };
二叉搜索树下的特殊子分类：平衡树
平衡树：二叉搜索树的任意结点的左右子树高度差绝对值都不大于 1
网络异常，图片无法展示
|
抓住其中的三个关键字：
- 任意结点
- 左右子树高度差绝对值都不大于 1
- 二叉搜索树
结论：递归！
var isBalanced = function (root) { if (!root) { return true; } // 先设置true，有一个高度不对就设置false，并返回 let flag = true; dfs_height(root); function dfs_height(root) { if (!root) { return 0; } let left_height = dfs_height(root.left); let right_height = dfs_height(root.right); // 高度不对，就return 0 不影响高度值，层层往上，最后外层函数就收到flag了 if (Math.abs(left_height - right) > 1) { flag = false; return 0; } else { return Math.max(left_height, right_height) + 1; } } return flag; };
构建平衡树
网络异常，图片无法展示
|
- 二叉搜索树的中序遍历是有序的
- 有序数组构建二叉搜索树
var balanceBST = function (root) { let nums = middle(root); return buildTree(nums); }; function middle(root) { if (!root) { return []; } let res = []; root.left && res.push(...middle(root.left)); res.push(root.val); root.right && res.push(...middle(root.right)); return res; } function buildTree(nums) { if (nums.length === 0) { return null; } let middle = Math.floor(nums.length / 2); let root = new TreeNode(nums[middle]); root.left = buildTree(nums.slice(0, middle)); root.right = buildTree(nums.slice(middle + 1)); return root; }
