二叉树 binary-tree
遇到一道二叉树的题目时的通用思考过程是：
1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个 traverse 函数配合外部变量来实现。
2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值。
3、无论使用哪一种思维模式，你都要明白二叉树的每一个节点需要做什么，需要在什么时候（前中后序）做。
二叉树种类
二叉搜索树
特点：
左边子树数值 < 当前值 < 右边子树数值 (root.left.val < root.val < root.rigth.val)
左子树上所有结点的值 <= 它根结点的值
右子树上所有结点的值 >= 它根结点的值
中序遍历的二叉搜索树一定是升序的
满二叉树
完全二叉树
平衡二叉树（AVL）
- 平衡二叉搜索树中每个结点的左子树和右子树的高度最多相差 1；
- 平衡二叉搜索树的子树也是平衡二叉搜索树；
- 一棵存有 n 个结点的平衡二叉搜索树的高度是 O(logn)。
其他概念
自顶向下为深度； 自底向上为高度；
深度遍历 DFS
遍历框架
funciton traverse(TreeNode root) {
if (root == null) {
return;
}
// 前序位置
traverse(root.left);
// 中序位置
traverse(root.right);
// 后序位置
}
先中后序基础
先序遍历
【快速排序】 遍历顺序：当前节点 -> 左边子节点 -> 右边子节点
中序遍历
主要用在 BST 场景。
特点：升序序列。
遍历顺序：左边子节点 -> 当前节点 -> 右边子节点
后序遍历
【归并排序】 遍历顺序：左边子节点 -> 右边子节点 -> 当前节点 后序遍历的最后一个节点为根节点
发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码。（力扣第 543 题「 二叉树的直径」）
先中后序递归与非递归
先序遍历-DLR
# 递归 O(n)
function inorderTraversal(root) {
const res = []
const findNode = (node) => {
if (node === null) return
res.push(node.val)
//递归遍历左子树
findNode(node.left)
//递归遍历右子树
findNode(node.right)
}
findNode(root)
return res
}
# 栈迭代 O(n)
function persentTraversal(root) {
if (root === null) return []
const res = []
const stk = []
while(root || stk.length > 0) {
while(root) {
stk.push(root)
res.push(root.val)
root = root.l
}
root = stk.pop()
root = root.r
}
return res
}
const root = [1,null,2,3]
> res = [1,2,3]
中序遍历-LDR
# 递归
function inorderTraversal1(root) {
if(root === null)return null
const res = []
function loop(p) {
if (!p) return
loop(p.l)
res.push(p.val)
loop(p.r)
}
loop(root)
return res
}
# 栈排序
function inorderTraversal(root) {
if(root === null)return null
const res = []
const stk = []
while(root || stk.length >0){
while(root) {
stk.push(root)
root = root.l
}
root = stk.pop()
res.push(root.val)
root = root.r
}
return res
}
后序遍历-LRD
#递归
function postOrderTraversal(root) {
if (!root) return null
const res = []
function loop(p) {
if(!p) return
loop(p.r)
loop(p.l)
res.push(p.val)
}
loop(root)
return res
}
# 栈
function postOrder(tree) {
const res = []
const stk = [tree]
while(stk.length) {
const node = stk.pop()
if (node.left) stk.push(node.left)
if (node.right) stk.push(node.right)
res.unshift(node.val)
}
return res
}
unshift 顺序插入是 DRL，故用 pop 先取 right,输出LRD
前中后序逆转
二叉树对称性递归的解题模板
1、递归结束条件：特殊情况的判断 如果是单树问题，一般来说只要进行以下判断：
if(!root) return true/false;
if(!root->left) return true/false/递归函数;
if(!root->right) return true/false/递归函数;
如果是双树问题(根节点分别为 p,q)，一般来说进行以下判断：
if(!p && !q)return true/false;
if(!p || !q)return true/false;
判断是否相同的树
const isSameTree = () => {
if (!q && !p) return true
return p && q &&
p.value === q.value &&
isSameTree(p.left, q.left) &&
isSameTree(p.right, q.right)
}