二叉树

本文最后更新于：2022年3月28日下午

树型结构

节点不能闭环
只有一个根节点
除了根节点，每个节点有且只有一个父节点
深度：节点到根节点的最长路径经过节点个数
高度：节点到叶节点最长路径经过节点个数
树的高度：根节点到叶节点的最长路径经过节点个数

最多只有两个子节点的树结构

二叉树是 n 个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成

平衡二叉树

任意节点的左右子树高度差不大于 1

满二叉树：每一层节点数都达到最大值

一个层数为 k 的满二叉树总结点数为：2^k-1
第 i 层上的结点数为：2^(i-1)
一个层数为 k 的满二叉树的叶子结点个数（也就是最后一层）：2^(k-1)

完全二叉树

一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。

二叉搜索树【BST】：右子大于父大于左子

二叉搜索树的中序遍历得到升序排列

二叉树遍历

function BinaryTree() {
	const Node = function (val) {
		this.val = val;
		this.left = null;
		this.right = null;
	};
	let root = null;
}

前序遍历

root -> left -> right

function preOrderTraverse(node) {
	let res = [];
	let stack = [];
	if(node) stack.push(node)
	while (stack.length > 0) {
		let curNode = stack.pop();
		res.push(curNode.val);
		curNode.right && stack.push(curNode.right); //  先右再左入栈
		curNode.left && stack.push(curNode.left); //  则左边先出栈
	}
	return res;
}

function preOrderTraverse(root){
	const res = []
	function traverse(node){
		if(!node) return 
		res.push(node.val)
		node.left && traverse(node.left)
		node.right && traverse(node.right)
	}
	traverse(root)
	return res
}

中序遍历

left -> root -> right

function inOrderTraverse(root){
	const res = []
	const stack = []
	let node = root
	while(node || stack.length){
		while(node){
			stack.push(node)
			node = node.left
		}
		node = stack.pop()
		res.push(node.val)
		node = node.right
	}
	return res
}

function inOrderTraverse(root){
	const res = []
	function traverse(node){
		if(!node) return 
		node.left && traverse(node.left)
		res.push(node.val)
		node.right && traverse(node.right)
	}
	traverse(root)
	return res
}

后序遍历

left -> right -> root

function postOrderTraverse(root){
	const res = []
	const stack = []
	if(root) stack.push(root)
	while(stack.length){
		const node = stack.pop()
		res.unshift(node.val)
		node.left && stack.push(node.left)
		node.right && stack.push(node.right)
	}
	return res
}


function postOrderTraverse(root){
	const res = []
	function traverse(node){
		if(!node) return 
		node.left && traverse(node.left)
		node.right && traverse(node.right)
		res.push(node.val)

	}
}

二叉树算法题

计算路径

// 输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。
function pathSum(root, sum) {
	if (!root) return [];
	if (root.value === sum) return [root.value];
	const paths = [];

	function searchPath(node, target, prePath) {
		const target = sum - node.val;
		const curPath = [...prePath, node.val];
		if (!node.left && !node.right && target === 0) {
			// 一直要到叶子结点
			paths.push(curPath);
			return;
		}
		node.left && searchPath(node.left, target, curPath);
		node.right && searchPath(node.right, target, curPath);
	}

	searchPath(root, sum, []);
	return paths;
}

二叉树镜像 / 翻转二叉树

// 递归
function mirrorTree(root){
  function mirror(node){
    if(!node) return
    [node.left,node.right] = [node.right,node.left]
    mirror(node.left)
    mirror(node.right)
  }
  mirror(root)
  return root
}

// stack
function mirrorTree(root){
  if(!root) return root
  const swap = node => [node.left,node.right] = [node.right,node.left]
  const stack = [root]
  while(stack.length>0){
    const node = stack.pop()
    swap(node)
    node.left && stack.push(node.left)
    node.right && stack.push(node.right)
  }
  return root
}

计算二叉树的最大深度

function TreeNode(val) {
	this.val = val;
	this.left = this.right = null;
}
// 后序遍历
// DFS
function maxDepth(root) {
	return root ? Math.max(maxDepth(root.left), maxDepth(root.right)) + 1 : 0;
	// 递归深度加1
	if (!root) return 0;
	const left = maxDepth(root.left);
	const right = maxDepth(root.right);
	return Math.max(left, right) + 1;
}

// BFS
//递归实现
function maxDepth(root) {
	let max = 0;
	if (!root) return max;
	function BFS(node, dep) {
		if (!node) return;
		max = Math.max(max, ++dep);
		BFS(node.left, dep);
		BFS(node.right, dep);
	}
	BFS(root, 0);
	return max;
}

// 栈实现
function maxDepth(root) {
	if (!root) return 0;
	const stack = [[root, 0]];
	let max = 0;
	while (stack.length > 0) {
		const [node, dep] = stack.pop();
		max = Math.max(max, dep + 1);
		node.left && stack.push(node.left, dep + 1);
		node.right && stack.push(node.right, dep + 1);
	}
	return max;
}

二叉搜素树中第 k 大的值

二叉搜索树 + 逆向中序遍历 => 降序排列 val

function kthLargest(root, k) {
	if (!root) return;
	let res = root.val;
	function DFS(node) {
		if (!node) return;
		DFS(node.right);
		if (--k === 0) {
			res = node.val;
			return;
		}
		DFS(node.right);
	}
	DFS(root);
	return res;
}

二叉树的最近公共祖先
对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）

function lowestCommonAncestor(root, p, q) {
	if (!root) return null;
	if (root === p || root === q) return root;
	const l = lowerCommonAncestor(root.left, p, q);
	const r = lowerCommonAncestor(root.right, p, q);
	l && r ? root : l || r;
}

二叉搜索树的最近公共祖先
二叉搜索树中 rightTree > root > leftTree

// 递归
function lowestCommonAncestor(root, p, q) {
	if (root.val < p.val && root.val < q.val) {
		return lowestCommonAncestor(root.right, p, q);
	}
	if (root.val > p.val && root.val > q.val) {
		return lowestCommonAncestor(root.left, p, q);
	}
	return root;
}

二叉搜索树节点间最小差

// 中序排列后，最小差就是该数组中相邻元素最小差

function minDiffInBST(root) {
	let pre = null;
	let min = Number.MAX_SAFE_INTEGER;
	function DFS(node) {
		if (!node) return;
		DFS(node.left);
		if (pre === null) {
			// init阶段
			pre = node.val;
		} else {
			min = Math.min(min, node.val - pre);
			pre = node.val;
		}
		// 中序列遍历，pre存储上一个值，由于BST特性，cur.val永远大于pre
		DFS(node.right);
	}
}

// 使用辅助栈
function minDiffInBST(root) {
	let pre = null;
	let min = Number.MAX_SAFE_INTEGER;
	const stack = [];
	while (root || stack.length > 0) {
		while (root) {
			stack.push(root);
			root = root.left;
		}
		const node = stack.pop();
		if (pre === null) {
			pre = node.val;
		} else {
			min = Math.min(min, node.val - pre);
			pre = node.val;
		}
		root = node.right;
	}
	return min;
}

层序遍历，打印二叉树
[[第一层],[第二层],[第三层]]

function  levelOrder (root) {
	const stack = [[root, 0]];
	const res = [];
	while (stack.length > 0) {
		const [node, level] = stack.shift();
		if (!node) break;
		if (!res[level]) res[level] = [];
		res[level].push(node.val);

		node.left && stack.push([node.left, level + 1]);
		node.right && stack.push(node.right, level + 1);
	}
	return res;
}

const levelOrder = function (root) {
	const stack = [root];
	const res = [];
	if (root) {
		while (stack.length > 0) {
			const preLevelSize = stack.length;
			const curLevel = [];
			for (let i = 0; i < preLevelSize; i++) {
				const n = stack.shift();
				if (!n) break;
				curLevel.push(n.val);
				n.left && stack.push(n.left);
				n.right && stack.push(n.right);
			}
			res.push(curLevel);
		}
	}

	return res;
};

判断平衡二叉树
平衡二叉树，左右子树深度差不大于 1

function isBalanced(root) {
	let res = true;
	function dfs(node) {
		if (!node) return 0;
		let left = dfs(node.left);
		let right = dfs(node.right);
		if (Math.abs(left - right) > 1) res = false;
		return Math.max(left, right) + 1;
	}
	dfs(root);
	return res;
}

function isBalanced(root) {
	function dfs(node) {
		if (!node) return false;
		const left = dfs(node.left);
		const right = dfs(node.right);
		if (Math.abs(left - right) > 1 || left === -1 || right === -1) return -1;
		return Math.max(left, right) + 1;
	}
	return dfs(root) !== -1;
}

判断对称二叉树

// 对称的二叉树
// l = r
// l.right = r.left && l.left = r.right
function isMirrorTree(root) {
	if (!root) return true;
	function recur(l, r) {
		if (l == null && r == null) return true;
		if (l == null || r == null || l !== r) return false;
		return recur(l.left, r.right) && recur(l.right, l, left);
	}
	return recur(root.left, root.right);
}

#javascript #算法

二叉树

http://yoursite.com/2022/02/24/二叉树/

作者

tatekii

发布于

2022年2月24日

许可协议

topK问题上一篇

作用域链与闭包下一篇