二叉树的中序遍历

对根节点的左子树进行中序遍历。 访问根节点。 对根节点的右子树进行中序遍历。

const bt = { val: 1, left: { val: 2, left: { val: 4, left: null, right: null, }, right: { val: 5, left: null, right: null, }, }, right: { val: 3, left: { val: 6, left: null, right: null, }, right: { val: 7, left: null, right: null, }, }, };

递归版

const inorder = (root) => { if(!root) {return;} inorder(root.left); console.log(root.val); inorder(root.right); } inorder(bt)

非递归版

const inorder = (root) => { if(!root) {return;} const stack = []; let p = root; while(stack.length || p){ while(p) { stack.push(p); p = p.left; } const n = stack.pop(); console.log(n.val); p = n.right } } inorder(bt) 4 2 5 1 6 3 7