JS构建二叉树后中序遍历
let line
let inputs = []
while (line = readline()) {
var lines = line.split(' ');
inputs.push(lines)
if(inputs.length == parseInt(inputs[0][0])+2){
let firstLine = inputs.shift()
let n = parseInt(firstLine[0])
let root = firstLine[1]
let node = inputs.pop()[0]
let Tree = buildTree(inputs)
order(Tree, node)
}
}
//定义二叉树class
function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
/**构建二叉树
传入tree = [[6, 3, 9],[3, 1, 4],[1, 0, 2],[2, 0, 0],[4, 0, 5],[5, 0, 0],[9, 8, 10],[10, 0, 0],[8, 7, 0],[7, 0, 0];**/
function buildTree(tree){
let map = {0:null}
for(let i = 0; i < tree.length; i++){
map[tree[i][0]] = new TreeNode(...tree[i])
}
for(let i = 0; i < tree.length; i++){
map[tree[i][0]].left = map[tree[i][1]]
map[tree[i][0]].right = map[tree[i][2]]
}
return map[tree[0][0]] //返回根节点
}
//前序遍历,传入已经构建的二叉树Tree
function order(Tree, node){
let orderList = []
let res = 0
const dfs = function(Tree){
if(!Tree) return
dfs(Tree.left)
orderList.push(Tree.val)
dfs(Tree.right)
}
dfs(Tree)
orderList.map((item, index)=>{
if(item == node){
res = index
}
})
console.log(res+1 >= orderList.length?0:orderList[res+1])
}