目录
(反)序列化二叉树(str<->tree):前序
前序遍历(迭代)/路径
stack.length
入栈:中右左
出栈:中左右
中序遍历(迭代)
cur||stack.length
后序遍历(迭代)
和前序遍历不同:
入栈:中左右
出栈:中右左
reverse出栈:左右中
层序遍历(BFS):可求树的深/高度
找树左下角的值:最后一行的最左边的值
判断完全二叉树
queue.length
flag = false; //是否遇到空节点
判断平衡二叉树
递归Math.max(getMaxDepth(root.left)+1,getMaxDepth(root.right)+1)
判断对称二叉树
递归deep(left.left, right.right) && deep(left.right, right.left)
翻转/生成镜像二叉树
递归交换左右
两节点的最近公共祖先
递归后序遍历
构造二叉树
从中序与前/后序遍历序列构造二叉树
最大二叉树:二叉树的根是数组中的最大元素(递归定义)
二叉搜索树:左<根<右(按中序遍历有序的树)
删除二叉搜索树中的节点
修剪二叉搜索树
有序数组转换为平衡二叉搜索树
left, right比arr.slice高效
Math.floor(left + (right - left) / 2)
最值、差值->有序数组的差值、最值
二叉搜索树的最小绝对差
二叉搜索树转换为累加树
(反)序列化二叉树(str<->tree):前序
function TreeNode(x) {this.val = x;this.left = null;this.right = null;
}
//反序列化二叉树:tree->str 把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串
function Serialize(pRoot, arr = []) {if (!pRoot) {arr.push("#");return arr;} else {arr.push(pRoot.val);//注意是val。而不是rootSerialize(pRoot.left, arr);Serialize(pRoot.right, arr);}return arr;
}
//序列化二叉树:str->tree 根据字符串结果str,重构二叉树
function Deserialize(s) {//转换为数组let arr = Array.isArray(s) ? s : s.split("");//取出vallet a = arr.shift();//构建二叉树结点let node = null;if (typeof a === "number") {//还有可能等于#node = new TreeNode(a);node.left = Deserialize(arr);node.right = Deserialize(arr);}return node;
}
module.exports = {Serialize: Serialize,Deserialize: Deserialize,
};
前序遍历(迭代)/路径
stack.length
入栈:中右左
出栈:中左右
/*** Definition for a binary tree node.* function TreeNode(val, left, right) {* this.val = (val===undefined ? 0 : val)* this.left = (left===undefined ? null : left)* this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number[]}*/
var preorderTraversal = function(root) {let stack=[]let res = []let cur = null;if(!root) return res;root&&stack.push(root)while(stack.length){cur = stack.pop()res.push(cur.val)cur.right&&stack.push(cur.right)cur.left&&stack.push(cur.left)}return res
};
中序遍历(迭代)
cur||stack.length
指针的遍历来帮助访问节点,栈则用来处理节点上的元素
/*** Definition for a binary tree node.* function TreeNode(val, left, right) {* this.val = (val===undefined ? 0 : val)* this.left = (left===undefined ? null : left)* this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number[]}*/
var inorderTraversal = function(root) {let stack = []let res = []let cur = rootwhile(cur||stack.length){if(cur){stack.push(cur)cur = cur.left} else {cur = stack.pop()res.push(cur.val)cur = cur.right}}return res
};
后序遍历(迭代)
和前序遍历不同:
入栈:中左右
出栈:中右左
reverse出栈:左右中
/*** Definition for a binary tree node.* function TreeNode(val, left, right) {* this.val = (val===undefined ? 0 : val)* this.left = (left===undefined ? null : left)* this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number[]}*/
var postorderTraversal = function(root) {let stack = []let res = []let cur = rootif(!root) return resstack.push(root)while(stack.length){cur = stack.pop()res.push(cur.val)cur.left&&stack.push(cur.left)cur.right&&stack.push(cur.right)}return res.reverse()};
层序遍历(BFS):可求树的深/高度
树的层序遍历,相似 图的广度优先搜索
- 初始设置一个空队,根结点入队
- 队首结点出队,其左右孩子 依次 入队
- 若队空,说明 所有结点 已处理完,结束遍历;否则(2)
/** function TreeNode(x) {* this.val = x;* this.left = null;* this.right = null;* }*//**** @param root TreeNode类* @return int整型二维数组*/
function levelOrder(root) {// write code hereif (root == null) {return [];}const arr = [];const queue = [];queue.push(root);while (queue.length) {const preSize = queue.length;const floor = [];//当前层for (let i = 0; i < preSize; ++i) {const v = queue.shift();floor.push(v.val);v.left&&queue.push(v.left);v.right&&queue.push(v.right);}arr.push(floor);}return arr;//[[1],[2,3]]
}
module.exports = {levelOrder: levelOrder,
};
找树左下角的值:最后一行的最左边的值
判断完全二叉树
queue.length
flag = false; //是否遇到空节点
完全二叉树:叶子节点只能出现在最下层和次下层,且最下层的叶子节点集中在树的左部。
/** function TreeNode(x) {* this.val = x;* this.left = null;* this.right = null;* }*/
/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可*** @param root TreeNode类* @return bool布尔型*/
function isCompleteTree(root) {// write code hereif (root == null) return true;const queue = [];queue.push(root);let flag = false; //是否遇到空节点while (queue.length) {const node = queue.shift();if (node == null) {//如果遇到某个节点为空,进行标记,代表到了完全二叉树的最下层flag = true;continue;}if (flag == true) {//若是后续还有访问,则说明提前出现了叶子节点,不符合完全二叉树的性质。return false;}queue.push(node.left);queue.push(node.right);}return true;
}
module.exports = {isCompleteTree: isCompleteTree,
};
判断平衡二叉树
平衡二叉树是左子树的高度与右子树的高度差的绝对值小于等于1,同样左子树是平衡二叉树,右子树为平衡二叉树。
递归Math.max(getMaxDepth(root.left)+1,getMaxDepth(root.right)+1)
/* function TreeNode(x) {this.val = x;this.left = null;this.right = null;
} */
function IsBalanced_Solution(pRoot)
{if(!pRoot) return true;// write code herereturn (Math.abs(getMaxDepth(pRoot.left) - getMaxDepth(pRoot.right)) <=1) && IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right)
}function getMaxDepth(root) {if(!root) return 0;return Math.max(getMaxDepth(root.left)+1,getMaxDepth(root.right)+1)
}
module.exports = {IsBalanced_Solution : IsBalanced_Solution
};
判断对称二叉树
递归deep(left.left, right.right) && deep(left.right, right.left)
/* function TreeNode(x) {this.val = x;this.left = null;this.right = null;
} */
let flag = true;
function deep(left, right) {if (!left && !right) return true; //可以两个都为空if (!right||!left|| left.val !== right.val) {//只有一个为空或者节点值不同,必定不对称return false;}return deep(left.left, right.right) && deep(left.right, right.left); //每层对应的节点进入递归比较
}
function isSymmetrical(pRoot) {return deep(pRoot, pRoot);
}
module.exports = {isSymmetrical: isSymmetrical,
};
翻转/生成镜像二叉树
递归交换左右
先序遍历
/** function TreeNode(x) {* this.val = x;* this.left = null;* this.right = null;* }*/
/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param pRoot TreeNode类 * @return TreeNode类*/
function Mirror( pRoot ) {function traversal(root){if(root===null) return ;//交换左右孩子let temp = root.left;root.left = root.right;root.right = temp;traversal(root.left);traversal(root.right);return root;}return traversal(pRoot);// write code here
}
module.exports = {Mirror : Mirror
};
两节点的最近公共祖先
如果从两个节点往上找,每个节点都往上走,一直走到根节点,那么根节点到这两个节点的连线肯定有相交的地方,
如果从上往下走,那么最后一次相交的节点就是他们的最近公共祖先节点。
递归后序遍历
/** function TreeNode(x) {* this.val = x;* this.left = null;* this.right = null;* }*//**** @param root TreeNode类* @param o1 int整型* @param o2 int整型* @return int整型*/
function dfs(root, o1, o2) {if (root == null || root.val == o1 || root.val == o2) {return root;}//递归遍历左子树let left = dfs(root.left, o1, o2);//递归遍历右子树let right = dfs(root.right, o1, o2);//如果left、right都不为空,那么代表o1、o2在root的两侧,所以root为他们的公共祖先if (left && right) return root;//如果left、right有一个为空,那么就返回不为空的那一个return left != null ? left : right;
}
构造二叉树
从中序与前/后序遍历序列构造二叉树
//前
var buildTree = function(preorder, inorder) {if (!preorder.length) return null;const rootVal = preorder.shift(); // 从前序遍历的数组中获取中间节点的值, 即数组第一个值const index = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标const root = new TreeNode(rootVal); // 创建中间节点root.left = buildTree(preorder.slice(0, index), inorder.slice(0, index)); // 创建左节点root.right = buildTree(preorder.slice(index), inorder.slice(index + 1)); // 创建右节点return root;
};
//后
var buildTree = function(inorder, postorder) {if (!inorder.length) return null;const rootVal = postorder.pop(); // 从后序遍历的数组中获取中间节点的值, 即数组最后一个值let rootIndex = inorder.indexOf(rootVal); // 获取中间节点在中序遍历中的下标const root = new TreeNode(rootVal); // 创建中间节点root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex)); // 创建左节点root.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex)); // 创建右节点return root;
};
最大二叉树:二叉树的根是数组中的最大元素(递归定义)
var constructMaximumBinaryTree = function (nums) {const BuildTree = (arr, left, right) => {if (left > right)return null;let maxValue = -1;let maxIndex = -1;for (let i = left; i <= right; ++i) {if (arr[i] > maxValue) {maxValue = arr[i];maxIndex = i;}}let root = new TreeNode(maxValue);root.left = BuildTree(arr, left, maxIndex - 1);root.right = BuildTree(arr, maxIndex + 1, right);return root;}let root = BuildTree(nums, 0, nums.length - 1);return root;
};
二叉搜索树:左<根<右(按中序遍历有序的树)
删除二叉搜索树中的节点
/*** Definition for a binary tree node.* function TreeNode(val, left, right) {* this.val = (val===undefined ? 0 : val)* this.left = (left===undefined ? null : left)* this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @param {number} key* @return {TreeNode}*/
var deleteNode = function(root, key) {if (!root) return null;if (key > root.val) {root.right = deleteNode(root.right, key);return root;} else if (key < root.val) {root.left = deleteNode(root.left, key);return root;} else {// 场景1: 该节点是叶节点if (!root.left && !root.right) {return null}// 场景2: 有一个孩子节点不存在if (root.left && !root.right) {return root.left;} else if (root.right && !root.left) {return root.right;}// 场景3: 左右节点都存在const rightNode = root.right;// 获取最小值节点const minNode = getMinNode(rightNode);// 将待删除节点的值替换为最小值节点值root.val = minNode.val;// 删除最小值节点root.right = deleteNode(root.right, minNode.val);return root;}
};
function getMinNode(root) {while (root.left) {root = root.left;}return root;
}
修剪二叉搜索树
修剪二叉搜索树,使得所有节点的值在[L, R]中 (R>=L)
var trimBST = function (root,low,high) {if(root === null) {return null;}if(root.val < low) {let right = trimBST(root.right, low, high);return right;}if(root.val > high) {let left = trimBST(root.left, low, high);return left;}root.left = trimBST(root.left, low, high);root.right = trimBST(root.right, low, high);return root;}
有序数组转换为平衡二叉搜索树
left, right比arr.slice高效
Math.floor(left + (right - left) / 2)
var sortedArrayToBST = function (nums) {const buildTree = (Arr, left, right) => {if (left > right)return null;let mid = Math.floor(left + (right - left) / 2);let root = new TreeNode(Arr[mid]);root.left = buildTree(Arr, left, mid - 1);root.right = buildTree(Arr, mid + 1, right);return root;}return buildTree(nums, 0, nums.length - 1);
};
最值、差值->有序数组的差值、最值
二叉搜索树的最小绝对差
二叉搜索树转换为累加树
一个有序数组[2, 5, 13],求从后到前的累加数组,也就是[20, 18, 13]
累加的顺序是右中左,所以我们需要反中序遍历这个二叉树,然后顺序累加
’东哥带你刷二叉树(思路篇) | labuladong 的算法笔记