二叉树

• 树中每个节点最多只能有两个子节点
• 在js中通常用object来模拟二叉树

二叉树为【1，2，3，4，5，6，7】

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: {
				val: 8,
				left: null,
				right: null
			}
		}
	}
}

先序遍历（根、左、右）

1. 访问根节点
2. 访问左子树（全部子节点全部完成）
3. 访问右子树

解题思路一：递归

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

1. 定义一个递归函数，循环遍历子节点
2. 递归结束条件为子节点为空
3. 先写入根元素
4. 如果有左子树，先写入左子树根元素，然后再判断有无左子树，如果有就继续【3，4】步骤
5. 如果没有左子树了，就写入右子树元素，然后判断有无右子树，继续【3，5步骤】

【1】先写入根元素[1]
【2】传入左子树[2,4,5],写入根元素[2]
【3】传入左子树[4],写入[4]
【4】没有左子树了，写入右子树[5]
【5】右子树递归调用……

var preorderTraversal = function(root) {
    if(!root) return []
    var stack = []
    // 定义一个递归函数，循环遍历子节点
    const preorder = function(rt) {
        if(!rt) {return} // 递归结束条件为子节点为空
        console.log(rt.val)
        stack.push(rt.val) // 写入当前节点值
        preorder(rt.left) // 把当前节点左子树递归调用，下次再继续写入根节点、左子树、右子树，如果没有左子树了递归就返回了执行右子树的递归了
        preorder(rt.right)// 把当前节点右子树递归调用，下次再继续写入根节点、左子树、右子树，
    }
    preorder(root)
    return stack;
}

解题思路二：迭代

上边我们使用递归来实现的先序遍历，现在我们就使用栈来模仿递归

作者：carlsun-2
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/dai-ma-sui-xiang-lu-chi-tou-qian-zhong-hou-xu-de-d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1. 使用栈来存储下次要访问的结构，前序遍历顺序为左、中、右
2. 每次把根节点压入栈中，
3. 迭代，当栈中有元素时，就出栈，访问节点值
4. 然后子树继续压入栈中，再弹出访问节点值
5. 因为栈是后进先出，所以先写右子树再写左子树

【1】先放入栈中整个树，访问值1
【2】右子树[3,6,7]放入栈中，左子树[2,4,5]再放入栈中
【3】先弹出[2,4,5]，然后访问值2，再访问其左子树4，最后没有左子树了只有右子树5
【4】最后再弹出右子树依如上有顺序访问

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */ 

 var preorderTraversal = function(root) {
    if(!root) {return []}
    const stack = [root] // 先把整个二叉树推进栈
    let res = [] 
    while(stack.length) {
         const n = stack.pop() // 先把元素弹出 
         res.push(n.val) // 将元素值写入结果
         if (n.right) stack.push(n.right) // 判断有无左右子树，如果有就写入，因为栈是后进先出，所以先写右子树
         if (n.left) stack.push(n.left) // 然后再写左子树
     }
     return res;
 };