根据一个数组（前序遍历、层次遍历）创建一个二叉树，并显示二叉树的左右视图。
尝试使用函数式编程，不使用class。
1. 定义二叉树节点
function BuildBiTreeNode(value = null, left = null, right = null) {
return {
value,
left,
right
};
}
2. 设置表示二叉树的两种Array（前序遍历、层序遍历）
假设有一个二叉树可以用以下两种Array来表示：
// pre 前序遍历
const input = ['1','2','4','7','#','#','8','9','#','#','#','#','3','5','#','#','6','#','10'];
// level 层序遍历
const input = ['1','2','3','4','-','5','6','7','8','-','-','-','10','-','-','9'];
二叉树如图所示：
二叉树示例
3. 定义MODE枚举
const MODE = {
PRE: 0, // 前序表示法
LEVEL: 1 // 层序表示法
};
4. 利用函数科里化对不同MODE返回不同构建二叉树的方法
function traverse(mode, flag) {
if (!Object.values(MODE).includes(mode)) throw TypeError('mode必须是BuildBiTree.MODE类型');
const _pre = arr => {
if (arr.length === 0) return;
const value = arr.pop();
if (value === flag) return null;
const node = BuildBiTreeNode(value);
node.left = _pre(arr);
node.right = _pre(arr);
return node;
};
const _level = (arr) => {
if (arr.length === 0) return;
let value = arr.pop();
let node = BuildBiTreeNode(value);
const root = node;
const level_arr = [node];
while (level_arr.length > 0) {
const curNode = level_arr.shift();
value = arr.pop();
if (value !== flag) {
if (typeof value === 'undefined') break;
node = BuildBiTreeNode(value);
curNode.left = node;
level_arr.push(node);
}
value = arr.pop();
if (value !== flag) {
if (typeof value === 'undefined') break;
node = BuildBiTreeNode(value);
curNode.right = node;
level_arr.push(node);
}
}
return root;
};
return {
[MODE.PRE]: _pre,
[MODE.LEVEL]: _level
}[mode];
}
5. 构建二叉树，并返回一个包含二叉树、左视图方法、右视图方法的对象
function BuildBiTree(input_array, mode=MODE.PRE, flag='#') {
if (typeof flag !== 'string') throw TypeError('flag必须是string类型');
if (!Array.isArray(input_array) || input_array.length === 0) return null;
const fn = traverse(mode, flag);
let tree = fn(input_array.slice().reverse());
tree.toJson = function(space) {
return JSON.stringify(this, undefined, space);
};
const _leftView = (root, level, viewArr) => {
if (!root) return;
if (level === viewArr.length) viewArr.push(root.value);
_leftView(root.left, level + 1, viewArr);
_leftView(root.right, level + 1, viewArr);
};
const _rightView = (root, level, viewArr) => {
if (!root) return;
if (level === viewArr.length) viewArr.push(root.value);
_rightView(root.right, level + 1, viewArr);
_rightView(root.left, level + 1, viewArr);
};
return {
tree,
leftView() {
const viewArr = [];
_leftView(this.tree, 0, viewArr);
return viewArr;
},
rightView() {
const viewArr = [];
_rightView(this.tree, 0, viewArr);
return viewArr;
}
};
}
BuildBiTree.MODE = MODE;
6. 测试效果
const input = ['1','2','4','7','#','#','8','9','#','#','#','#','3','5','#','#','6','#','10']; // pre 前序遍历
// const input = ['1','2','3','4','-','5','6','7','8','-','-','-','10','-','-','9']; // level 层序遍历
const myTree = BuildBiTree(input, BuildBiTree.MODE.PRE, '#');
console.log('tree: ', myTree.tree.toJson(2));
console.log('left view: ', myTree.leftView());
console.log('right view: ', myTree.rightView());
