二叉树的先序遍历

先序遍历算法口诀

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

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 preorder = (root) => { if(!root) {return;} console.log(root.val) preorder(root.left) preorder(root.right) } preorder(bt)

非递归版

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