用JavaScript实现树的前序、中序、后续查询以及高度计算

class TreeNode {
    constructor (value) {
        this.value = value;
        this.left = this.right = null;
    }
}

var maxDepth = function(troot) {
    if (!troot) {
        return 0;
    }

    const left = maxDepth(troot.left);
    const right = maxDepth(troot.right);
    return Math.max(left, right) + 1;
}

var preOrder = function(root) {
	if (!root) {
		return;
	}
	console.log(root.value);
	preOrder(root.left);
	preOrder(root.right);
}

var preOrderWithoutRescursion = function(root) {
	let stack = [];
	let pointNode = root;

	while(pointNode || stack.length > 0) {
		while(pointNode) {
			console.log(pointNode.value);
			stack.push(pointNode);
			pointNode = pointNode.left;
		}

		if (stack.length > 0) {
			pointNode = stack.pop();
			pointNode = pointNode.right;
		}
	}
}

var midOrder = function(root) {
	if (!root) {
		return;
	}
	midOrder(root.left);
	console.log(root.value);
	midOrder(root.right);
}

var midOrderWithoutRescursion = function(root) {
	let stack = [];
	let pointNode = root;

	while(pointNode || stack.length > 0) {
		while(pointNode) {
			stack.push(pointNode);
			pointNode = pointNode.left;
		}

		if (stack.length > 0) {
			pointNode = stack.pop();
			console.log(pointNode.value);
			pointNode = pointNode.right;
		}
	}
}

var postOrder = function(root) {
	if (!root) {
		return;
	}
	postOrder(root.left);
	postOrder(root.right);
	console.log(root.value);
}

var postOrderWithoutRescursion = function(root) {
	let stack = [];
	let pointNode = root;
	let right = root;

	while(pointNode || stack.length > 0) {
		if (pointNode) {
			stack.push(pointNode);
			pointNode = pointNode.left;
		} else {
			pointNode = stack.length > 0 ? stack[stack.length - 1] : null;
			if (pointNode.right && pointNode.right != right) {
				pointNode = pointNode.right;
			} else{
				pointNode = stack.pop();
				console.log(pointNode.value);
				right = pointNode;
				pointNode = null;
			}
		}
	}
}

var levelOrder = function(root) {
	if (!root) {
		return;
	}

	let queue = [];
	queue.unshift(root);

	while(queue.length > 0) {
		let pointNode = queue.pop();
		console.log(pointNode.value);

		if (pointNode.left) {
			queue.unshift(pointNode.left)
		}

		if (pointNode.right) {
			queue.unshift(pointNode.right);
		}		
	}
}

var tree = new TreeNode(3);
tree.left = new TreeNode(9);
tree.right = new TreeNode(20);
tree.right.left = new TreeNode(15);
tree.right.right = new TreeNode(7);

let depth = maxDepth(tree);
console.log("depth:"+depth);

console.log("pre order:");
preOrder(tree);

console.log("mid order:");
midOrder(tree)

console.log("post order:");
postOrder(tree)

console.log("pre order without recursion");
preOrderWithoutRescursion(tree);

console.log("mid order without recursion");
midOrderWithoutRescursion(tree);

console.log("post order without recursion");
postOrderWithoutRescursion(tree);

console.log("level order");
levelOrder(tree);

运行结果：

depth:3
pre order:
3
9
20
15
7
mid order:
9
3
15
20
7
post order:
9
15
7
20
3
pre order without recursion
3
9
20
15
7
mid order without recursion
9
3
15
20
7
post order without recursion
9
15
7
20
3
level order
3
9
20
15
7