Day 19：二元树遍历 Binary Tree Traversal

今天一起来认识二元树的三种遍历方式吧！
但是别急！我们先来认识二元搜寻树BST的定义！

二元搜寻树是一棵二元树，如果不为空（二元树可以为空！）
则须满足:

1. 左子树所有节点(Nodes)的值都要小於Root
2. 右子树所有节点(Nodes)的值都要大於或等於Root
3. 它的左右子树也都要是BST
   

我们以这张图为例
我们预期三种不同的结果如下

1. 中序 In-order: [1, 2, 10, 15, 20, 20, 22]
2. 前序 pre-order: [ 20, 10, 2, 1, 15, 20, 22]
3. 後序 post-order: [1, 2, 15, 10, 22, 20, 20]

我们可以从结果观察到：中序追踪可以恰好得到由小到大排列好的结果！
中序的行为其实就是 “左中右”的感觉
同理
前序 → 中左右
後序 → 左右中
也就是说
"中"就是我们当下拜访到的当下结点，"左"就是左儿子（left child），"右"则是右儿子
有没有发现这三个名称其实是跟去“中”在前中後下去命名的感觉(我都是这样记的～)

而它程序码的实现也会是依照着个逻辑下去走！
像是中序追踪，其实就是：

inOrderTraverse(left)
array.append(current.value)
inOrderTraverse(rigtht)

以这张图为例，我们一开始从20开始不断往左边走到1，而後发先1没有左子树和右子树，我们就把他加到阵列。
接着退回2，并把2加到阵列，发现2没有右子树又退回去2，继续类似的路径，再退回去10...以此类推。这就是中序追踪的行为！

规则讲到这里我们来挑战题目吧！

/**
 * 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[]}
 */
    
function inOrderTraverse(tree, array) {
  if(tree !== null ){
		inOrderTraverse(tree.left, array);
		array.push(tree.val);
		inOrderTraverse(tree.right, array);
	}
	return array;
}

var inorderTraversal = function(root) {
    const array = [] ;
    if(!root) return array;
    inOrderTraverse(root,array);
	return array;
};

做完inorder的题目，别忘了自己推一下preorder以及postorder，也都是leetCode里面的题目喔！
今天等於完成了三题！
下面作法

function preOrderTraverse(tree, array) {
    if(tree !== null ){
		array.push(tree.value);
		preOrderTraverse(tree.left, array);
		preOrderTraverse(tree.right, array);
	}
	return array;
}

function postOrderTraverse(tree, array) {
  if(tree !== null ){
		postOrderTraverse(tree.left, array);
		postOrderTraverse(tree.right, array);
		array.push(tree.value);
	}
	return array;
}

明日预告： 认识了前中後序的走访，来试试实作深度追踪吧！