树这种数据结构包括根节点 root，左右节点，子树中又有父节点，子节点，兄弟节点，没有子节点的成为叶子节点，树分为二叉树和多叉树
List 就是特殊化的 tree，Tree就是特殊化的Graph
二分搜索树
二分搜索树（英语：Binary Search Tree），也称为 有序二叉树或排序二叉树。满足以下几个条件：
二分搜索树的优势：不仅可以查找数据，还可以高效的插入、删除数据
注意二分搜索树不一定是完全二叉树
树的遍历
前序：根-左-右
中序：左-根-右
后序：左-右-根
给你一个二叉树的根节点 root ， 检查它是否轴对称。
示例 1：
输入：root = [1,2,2,3,4,4,3]输出：true 示例 2：
输入：root = [1,2,2,null,3,null,3]输出：false
提示：
树中节点数目在范围 [1, 1000] 内-100 <= Node.val <= 100
进阶：你可以运用递归和迭代两种方法解决这个问题吗？
方法 1.dfs 递归
js：
var isSymmetric = function(root) { if(!root) return true const isMirror = (l, r) => { if(!l && !r) return true; //两个空节点也为镜像 if( l && r && l.val === r.val && //左节点和右节点相同，左子树和右子树也对称则返回true isMirror(l.left, r.right) && isMirror(l.right, r.left) ) { return true; } return false; } return isMirror(root.left, root.right)};
复制代码
方法 2.bfs
js：
function isSymmetric(root) { const isMirror = (l, r) => { const queue = [l, r]; while (queue.length) { const u = queue.shift(); const v = queue.shift(); if (!u && !v) continue; //两个空节点也为镜像 //左右节点只有一个节点为空，或者值不相同返回false if (!u || !v || u.val !== v.val) return false; queue.push(u.left, v.right); //加入左节点的左子树，右节点的右子树 queue.push(v.left, u.right); //加入右节点的左子树，左节点的右子树 } return true; }; return isMirror(root.left, root.right);}
复制代码
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]输出：true 示例 2：
输入：p = [1,2], q = [1,null,2]输出：false 示例 3：
输入：p = [1,2,1], q = [1,1,2]输出：false
提示：
两棵树上的节点数目都在范围 [0, 100] 内-104 <= Node.val <= 104
方法 1.dfs 递归
js:
var isSameTree = function(p, q) { if(p == null && q == null) //都是null表示相同 return true; if(p == null || q == null) //只有一个是null表示不同 return false; if(p.val != q.val) //节点的值不同 return false; return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);//递归左右子树};
复制代码
方法 2bfs：
js：
var isSameTree = function(p, q) { let pQ = [p], qQ = [q], res = true
while (pQ.length) { pNode = pQ.shift() qNode = qQ.shift()
if (pNode === null && qNode === null) { res = true } else if (pNode === null || qNode === null) { res = false break } else { if (pNode.val !== qNode.val) { res = false break } else { pQ.push(pNode.left) pQ.push(pNode.right)
qQ.push(qNode.left) qQ.push(qNode.right) } } }
return res};
复制代码
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例 1：
输入：root = [1,2,3,null,null,4,5]输出：[1,2,3,null,null,4,5]示例 2：
输入：root = []输出：[]示例 3：
输入：root = [1]输出：[1]示例 4：
输入：root = [1,2]输出：[1,2]
提示：
树中结点数在范围 [0, 104] 内-1000 <= Node.val <= 1000
方法 1.递归 dfs
思路：深度优先遍历，按根,左,右 返回字符串，方便反序列化的时候从根节点开始构建，递归左右子树，直到遇见了 null 节点。
复杂度：时间复杂度O(n)，每个节点访问一次，n 是树的节点个数。空间复杂度O(n)，最坏情况下递归深度是 n
js：
const serialize = (root) => { if (root == null) { //遇到null 返回‘X’进行标示 return 'X'; } const left = serialize(root.left); //序列化左子树 const right = serialize(root.right); //序列化右子树 return root.val + ',' + left + ',' + right; //按根,左,右 返回字符串};
const deserialize = (data) => { const list = data.split(','); //字符串转数组
const buildTree = (list) => { //构建树 const rootVal = list.shift(); //第一个元素 if (rootVal == "X") { //如果是X，返回null return null; } const root = new TreeNode(rootVal); //如果不是X就创建节点 root.left = buildTree(list); //构建左子树 root.right = buildTree(list); //构建右子树 return root; //返回构建的节点 };
return buildTree(list);};
复制代码
方法 2:bfs
动画过大，点击查看
js：
const serialize = (root) => { const queue = [root]; let res = []; while (queue.length) { const node = queue.shift(); //出队 if (node) { //node存在 推入根左右 res.push(node.val); queue.push(node.left); queue.push(node.right); } else { //如果不存在 推入‘x’ res.push('X'); } } return res.join(','); //数组转成字符串}
const deserialize = (data) => { if (data == 'X') return null;
const list = data.split(','); //字符串转数组
const root = new TreeNode(list[0]); //从队首开始构建 const queue = [root]; //根节点加入队列 let cursor = 1; //遍历到了第几个节点
while (cursor < list.length) { //当队列没遍历完时 const node = queue.shift(); //出队
const leftVal = list[cursor]; //左节点的值 const rightVal = list[cursor + 1]; //右节点的值
if (leftVal != 'X') { //不是空节点 const leftNode = new TreeNode(leftVal); //构建左节点 node.left = leftNode; //左节点挂在父节点的left下 queue.push(leftNode); //自己入列 构建以自己为根的子树 } if (rightVal != 'X') { const rightNode = new TreeNode(rightVal); node.right = rightNode; queue.push(rightNode); } cursor += 2; //构建的节点数+2 } return root; //返回根};
复制代码
给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [1,2,3,null,5]输出：["1->2->5","1->3"]示例 2：
输入：root = [1]输出：["1"]
提示：
树中节点的数目在范围 [1, 100] 内-100 <= Node.val <= 100
方法 1:dfs
js:
var binaryTreePaths = function(root) { const paths = []; const dfs = (root, path) => {//传入递归的节点和路径数组 if (root) { path += root.val.toString();//加入当前节点 //叶子结点就将所有连接起来的节点字符串加入paths中 也就是其中一条路径 if (root.left === null && root.right === null) { paths.push(path); } else { path += "->"; //不是叶子节点继续递归左右子树 dfs(root.left, path); dfs(root.right, path); } } } dfs(root, ""); return paths;};
复制代码
方法 2:bfs
动画过大，点击查看
js:
var binaryTreePaths = function(root) { const res = []; if (root === null) { return res; } const nodes = [root]; const paths = [root.val.toString()];
while (nodes.length) { const node = nodes.shift(); const path = paths.shift();
if (node.left === null && node.right === null) {//叶子节点 res.push(path); } else { if (node.left !== null) {//左节点不为空 加入队列 nodes.push(node.left); paths.push(path + "->" + node.left.val.toString()); }
if (node.right !== null) {//右节点不为空 加入队列 nodes.push(node.right); paths.push(path + "->" + node.right.val.toString()); } } } return res;};
复制代码
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。
示例 1：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 输出：true 解释：等于目标和的根节点到叶节点路径如上图所示。示例 2：
输入：root = [1,2,3], targetSum = 5 输出：false 解释：树中存在两条根节点到叶子节点的路径：(1 --> 2): 和为 3(1 --> 3): 和为 4 不存在 sum = 5 的根节点到叶子节点的路径。示例 3：
输入：root = [], targetSum = 0 输出：false 解释：由于树是空的，所以不存在根节点到叶子节点的路径。
提示：
树中节点的数目在范围 [0, 5000] 内-1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
js：
const hasPathSum = (root, sum) => { if (root == null) {//递归终止条件 return false; } if (root.left == null && root.right == null) {//遍历到叶子节点 return sum - root.val == 0; //sum正好减少到了0 返回ture 否则返回false } //递归左右子树，有一个返回true就找到了一条这样的路径 return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);}
复制代码
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
输入：root = [3,9,20,null,null,15,7]输出：[[15,7],[9,20],[3]]示例 2：
输入：root = [1]输出：[[1]]示例 3：
输入：root = []输出：[]
提示：
树中节点数目在范围 [0, 2000] 内-1000 <= Node.val <= 1000
时间复杂度O(n)，空间复杂度O(n)
js：
const levelOrderBottom = (root) => { if (root == null) { return []; } const queue = []; queue.push(root); const res = [];
while (queue.length) { const subRes = []; const levelSize = queue.length; for (let i = 0; i < levelSize; i++) { const cur = queue.shift(); subRes.push(cur.val); if (cur.left) { queue.push(cur.left); } if (cur.right) { queue.push(cur.right); } } res.unshift(subRes);//和102不一样的地方 推入res中的方向正好相反 } return res;}
复制代码
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7]输出：[[3],[9,20],[15,7]]示例 2：
输入：root = [1]输出：[[1]]示例 3：
输入：root = []输出：[]
提示：
树中节点数目在范围 [0, 2000] 内-1000 <= Node.val <= 1000
方法 1.广度优先遍历
动画过大，点击查看
Js:
var levelOrder = function(root) { const ret = []; if (!root) { return ret; }
const q = []; q.push(root);//初始队列 while (q.length !== 0) { const currentLevelSize = q.length;//当前层节点的数量 ret.push([]);//新的层推入数组 for (let i = 1; i <= currentLevelSize; ++i) {//循环当前层的节点 const node = q.shift(); ret[ret.length - 1].push(node.val);//推入当前层的数组 if (node.left) q.push(node.left);//检查左节点，存在左节点就继续加入队列 if (node.right) q.push(node.right);//检查左右节点，存在右节点就继续加入队列 } }
return ret;};
复制代码
方法 2：深度优先遍历
动画过大，点击查看
js:
var levelOrder = function(root) { if(!root) return [] let res = [] dfs(root, 0, res) return res};
function dfs(root, step, res){//每层透传当前节点，层数，和输出数组 if(root){ if(!res[step]) res[step] = []//初始化当前层数组 res[step].push(root.val)//当前节点加入当前层数组 dfs(root.left, step + 1, res)//step+1，递归左节点 dfs(root.right, step + 1, res)//step+1，递归右节点 }}
复制代码
给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例 1:
输入: [1,2,3,null,5,null,4]输出: [1,3,4]示例 2:
输入: [1,null,3]输出: [1,3]示例 3:
输入: []输出: []
提示:
二叉树的节点个数的范围是 [0,100]-100 <= Node.val <= 100
方法 1:dfs
js：
var rightSideView = function (root) { function dfs(root, step, res) {//传入根节点 层数 右视的节点的数组 if (root) { if (res.length === step) { res.push(root.val); //当res长度和step相等时 当前节点就是这一层的右节点 加入数组中 } dfs(root.right, step + 1, res); //先递归右节点 让它在下一层先被处理 dfs(root.left, step + 1, res); } } if (!root) return []; let arr = []; dfs(root, 0, arr); return arr;};
复制代码
方法 2:bfs
js：
var rightSideView = function (root) { if (!root) return []; let queue = [root]; //广度优先遍历的队列 首先加入root let arr = []; //存放右视的节点 while (queue.length > 0) { let len = queue.length; while (len) { let node = queue.shift(); //取出队列第一个元素 if (len === 1) arr.push(node.val); //当当前层长度等于1时 说明是最边的节点 if (node.left) queue.push(node.left); //继续向队列中添加左右节点 if (node.right) queue.push(node.right); len--;//出队之后 当前层长度减1 } } return arr;};
复制代码
动画过大，点击查看
动画过大，点击查看
动画过大，点击查看
动画过大，点击查看
方法 1.递归
js:
//时间复杂度O(n),n为节点个树，空间复杂度O(n)，即递归的空间开销(树的高度)，最坏的情况下树是链表，所以是O(n)，平均空间复杂度O(logn)//前序遍历:var preorderTraversal = function(root, res = []) { if (!root) return res; res.push(root.val); preorderTraversal(root.left, res) preorderTraversal(root.right, res) return res;};
//中序遍历:var inorderTraversal = function(root, res = []) { if (!root) return res; inorderTraversal(root.left, res); res.push(root.val); inorderTraversal(root.right, res); return res;};
//后序遍历:var postorderTraversal = function(root, res = []) { if (!root) return res; postorderTraversal(root.left, res); postorderTraversal(root.right, res); res.push(root.val); return res;};
复制代码
方法 2.迭代
js:
// 时间复杂度O(n),n为节点个树，空间复杂度O(n)，显示栈的空间开销
// 前序遍历：中左右// 压栈顺序：右左中var preorderTraversal = function(root, res = []) { const stack = []; if (root) stack.push(root); while(stack.length) { const node = stack.pop(); if(!node) { res.push(stack.pop().val); continue; } if (node.right) stack.push(node.right); // 右 if (node.left) stack.push(node.left); // 左 stack.push(node); // 中 stack.push(null); }; return res;};
// 中序遍历：左中右// 压栈顺序：右中左var inorderTraversal = function(root, res = []) { const stack = []; if (root) stack.push(root); while(stack.length) { const node = stack.pop(); if(!node) { res.push(stack.pop().val); continue; } if (node.right) stack.push(node.right); // 右 stack.push(node); // 中 stack.push(null); if (node.left) stack.push(node.left); // 左 }; return res;};
// 后续遍历：左右中// 压栈顺序：中右左var postorderTraversal = function(root, res = []) { const stack = []; if (root) stack.push(root); while(stack.length) { const node = stack.pop(); if(!node) { res.push(stack.pop().val); continue; } stack.push(node); // 中 stack.push(null); if (node.right) stack.push(node.right); // 右 if (node.left) stack.push(node.left); // 左 }; return res;};
复制代码
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：给定二叉树 [3,9,20,null,null,15,7]，
3
/
9 20 /
15 7 返回它的最大深度 3 。
方法 1.dfs
动画过大，点击查看
思路：一个节点的深度等于 1 加左节点和有节点深度的较大者，用公式表示 h(r)=Math.max(h(r.left), h(right)) + 1，所以可以深度遍历左右子树，返回左右子树的最大深度。
复杂度分析：时间复杂度O(n), 其中 n 为二叉树节点的个数。空间复杂度O(n), 其中 n 表示二叉树的高度，最坏的情况下和树的节点数相同
js:
var maxDepth = function(root) { if(!root) { return 0; } else { const left = maxDepth(root.left);//递归左子树 const right = maxDepth(root.right);//递归右子树 return Math.max(left, right) + 1;//1加左节点和有节点深度的较大者 }};
复制代码
方法 2.bfs
动画过大，点击查看
思路：层序遍历二叉树，每层结束的时候 depth 加 1.
复杂度分析：时间复杂度O(n)，n 为二叉树的节点个数，每个节点只会被访问一次。空间复杂度O(n),表示队列中存放的元素，最坏情况下和二叉树节点个数一样
Js:
const maxDepth = (root) => { if (root == null) return 0; const queue = [root]; let depth = 1; while (queue.length) { // 当前层的节点个数 const levelSize = queue.length; // 逐个让当前层的节点出列 for (let i = 0; i < levelSize; i++) { // 当前出列的节点 const cur = queue.shift(); // 左右子节点入列 if (cur.left) queue.push(cur.left); if (cur.right) queue.push(cur.right); } // 当前层所有节点已经出列，如果队列不为空，说明有下一层节点，depth+1 if (queue.length) depth++; } return depth;};
复制代码
视频讲解：传送门
评论