二叉树

二叉树的概念

树，有三个比较相似的概念：高度，深度，层；它们的定义为：

1. 节点的高度：节点到叶子节点的最长路径
2. 节点的深度：根节点到这个节点所经历的边的个数
3. 节点的层数：节点的深度 + 1

二叉树是一种特殊的树，即：树中每个节点的分叉数不大于2的有序树。
二叉树是一棵树，是一棵由一个根节点和两棵互不相交的，分别称为左子树和右子树的非空树；左右子树也是二叉树。

二叉树前序遍历

方法1. 递归遍历法

let  preorderTraversal = function(root){
  if(!root){
   return []
  }
 let left = preorderTraversal(root.left)
 let right = preorderTraversal(root.right)
 return [root.val, ...left, ...right]
}

方法2. 迭代的方式
实现思路
初始化一个栈和结果数组，将根节点放进入栈中，当栈不为空的时候，重复下面的步骤

1. 取出栈顶元素top, 访问top
2. 若top的右子节点不为空，将top的右子节点放入栈中
3. 若top的左子节点不为空，将top的左子节点放入栈中
4. 将取出的栈顶元素top放进入结果数组

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
var preorderTraversal = function(root){
  if(!root){
       return [];
  }
let result = []
let stack = [root]
while(stack.length){
  let top =stack.pop();
   if(top.right){
     stack.push(top.right)
    }
   if(top.right){
     stack.push(top.right)
    }
   if(top.left){
     stack.push(top.left)
    }
   result.push(root.val)
  }
}