js前端算法---树 深度优先遍历 广度优先遍历 实现

深度优先遍历 广度优先遍历

const tree = {
	val:'a',
	children:[
		{
			val:'b',
			children:[
				{val:'d',children:[]},
				{val:'e',children:[]},
			]
		},
		{
			val:'c',
			children:[
				{val:'f',children:[]},
				{val:'g',children:[]}
			]
		}
	]
}

//深度优先遍历
const fun1 = (root)=>{
	console.log( root.val );
	root.children.forEach( fun1 );
}
fun1(tree);


//广度优先遍历
const fun2 = (root)=>{
	const arr = [root];
	while( arr.length > 0 ){
		const o = arr.shift();
		console.log( o.val );
		o.children.forEach(item=>{
			arr.push( item );
		})
	}
}
fun2(tree);

前、中、后序是指根节点但位置

1.二叉树的前序遍历144

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
输入：root = [1,null,2,3]
输出：[1,2,3]

//递归
var preorderTraversal = function(root) {
	let arr = [];
	var fun = ( node )=>{
		if( node ){
			//先根节点
			arr.push( node.val );
			//遍历左子树
			fun( node.left );
			//遍历右子树
			fun( node.right );
		}
	}
	fun( root );
	return arr;
};
//非递归
var preorderTraversal = function(root) {
    let stack=[]
    let arr=[]
    if(root){stack.push(root)}
    while(stack.length>0){
        let o=stack.pop()
        arr.push(o.val)
        o.right&&stack.push(o.right)
        o.left&&stack.push(o.left)
    }
    return arr
};

2.二叉树的中序遍历

//递归
var inorderTraversal = function(root) {
	const arr = [];
	const fun = ( root )=>{
		if( !root ) return;
		fun( root.left );
		arr.push( root.val );
		fun( root.right );
	}
	fun( root );
	return arr;
};
// console.log( inorderTraversal(tree) );
//非递归
var inorderTraversal = function(root) {
	const arr = [];
	const stack = [];
	let o = root;
	while( stack.length || o ){
		while( o ){
			stack.push( o );
			o = o.left;
		}
		const n = stack.pop();
		arr.push( n.val );
		o = n.right;
	}
	return arr;

}

2.二叉树的后序遍历

//递归
var postorderTraversal = function(root) {
	const arr = [];
	const fun = ( node )=>{
		if( node ){
			fun( node.left );
			fun( node.right );
			arr.push(  node.val );
		}
	}
	fun( root );
	return arr;
};
// console.log( postorderTraversal(tree) );
//非递归
var postorderTraversal = function(root) {
	if( !root ) return [];
	let arr = [];
	let stack = [root];
	while( stack.length ){
		const o = stack.pop();
		arr.unshift( o.val );
		o.left && stack.push( o.left );
		o.right && stack.push( o.right );
	}
	return arr;
}

111.二叉树的最小深度

var minDepth = function(root) {
	if( !root ) return 0;
	const stack = [ [root,1] ];
	while(  stack.length ){
		const [o,n] = stack.shift();
		if( !o.left && !o.right ){
			return n;
		}
		if( o.left ) stack.push(  [o.left,n+1] );
		if( o.right ) stack.push(  [o.right,n+1] );
	}
};

104.二叉树最大深度

var maxDepth = function(root) {
	if( !root ) return 0;
	const stack = [root];
	let num = 0;
	while( stack.length ){
		let len = stack.length;
		num++;
		while( len-- ){
			const o = stack.shift();
			o.left && stack.push(  o.left );
			o.right && stack.push(  o.right );
		}
	}
	return num;
};

226.翻转二叉树

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点

var invertTree = function(root) {

	if(  root == null ) return null;

	let tmp = root.left;
	root.left = root.right;
	root.right = tmp;
	invertTree(root.left);
	invertTree(root.right);
	return root;

};

100.相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

输入：p = [1,2,3], q = [1,2,3] 输出：true

var isSameTree = function(p, q) {
	if( p === null && q === null ) return true;
	if( p === null || q === null ) return false;
	if( p.val !== q.val ) return false;
	return isSameTree( p.left , q.left ) && isSameTree( p.right , q.right );
};