树的相关操作

144. 前序遍历
     时间复杂度： O（n）
     空间复杂度：O（n）

var preorderTraversal = function(root) {
    var stack = []
    var nodes = []
    var p = root
    while( stack.length != 0 || p != null){
        if(p != null){
            stack.push(p)
            nodes.push(p.val)
            p = p.left
        }else{
            var node = stack.pop()
            p = node.right
        }
    }
    return nodes
};

94.中序遍历

var inorderTraversal = function(root) {
    var stack = []
    var nodes = []
    var p = root
    while(stack.length != 0 || p != null){
        if(p != null){
            stack.push(p)
            p =p.left
        }else{
            var node = stack.pop()
            nodes.push(node.val)
            p = node.right
        }
    }
    return nodes
};

145.后序遍历

var postorderTraversal = function(root) {
    var stack = []
    var nodes = []
    var p = root
    while(stack.length != 0 || p != null){
        if(p != null){
            stack.push(p)
            nodes.unshift(p.val)
            p =p.right
        }else{
            var node = stack.pop()
            p = node.left
        }
    }
    return nodes
};

102. 层序遍历
     思路：二叉树的层序遍历通过队列进行，先将根节点入队，进入循环；
     判断队列是否为空，将元素一个一个出队，将子女一个一个入队，每次出队的元素都为一个层次中的。

var levelOrder = function(root) {
    var nodes = []
    var queue = []
    if(root == null) return nodes
    queue.push(root)
    while(queue.length != 0){
        var temp = []  
        var n = queue.length
        for(var i = 0; i< n; i++){
            var node = queue.shift()
            temp.push(node.val)
            if(node.left!=null) queue.push(node.left)
            if(node.right!=null) queue.push(node.right)
        }
        nodes.push(temp)
    }
    return nodes
};