二叉树的前序遍历

2022-04-14  本文已影响0人  Shiki_思清

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

image.png

[1,7,8,null,2,3,4,2,3,4,null,5]
提示:

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

/**
 * 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) {
    var newArrL = [],  newArrR = []
    if (!root || root.length == 0) {return []}
    if (root.left == null && root.right == null ) {
        return [root.val]
    } else {
        if (root.left != null)  {
            let temp = preorderTraversal(root.left)
            newArrL = newArrL.concat(temp) 
        }
        if (root.right != null)  {
            let temp = preorderTraversal(root.right)
            newArrR = newArrR.concat(temp) 
        } 
    }
    const newa = [root.val].concat(newArrL, newArrR)
    return newa
};

进阶:递归算法很简单,你可以通过迭代算法完成吗?

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {

    let queue = []
    let arr = []
    while(root) {
        queue.push(root)
        arr.push(root.val)
        root = root.left
    }
    
    
    let next = function() {
        root = queue.pop()
        if (root.right) {
            root = root.right
            while(root) {
                queue.push(root)
                arr.push(root.val)
                root = root.left
            }
        }
    }
    let hasNext = function() {
        return queue.length > 0
    }

    while(hasNext()){
        next()
    }
    return arr
}

上一篇 下一篇

猜你喜欢

热点阅读