二叉树

作者:江月迟迟

发表于:2024-12-10

字数统计:859 字

预计阅读3分钟

遍历

前序遍历

递归

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal1 = function(root) {
    const result = []
    traverse(root)
    return result

    function traverse(node) {
        // 中、左、右
        if(!node) return
        result.push(node.val)
        traverse(node.left)
        traverse(node.right)
    }
};

迭代

// 迭代，出栈处理拦截
var preorderTraversal2 = function(root) {
    const result = [], stack = []
    if(!root) return result
    // 处理中结点，入栈：右、左
    stack.push(root)
    while(stack.length) {
        const node = stack.pop()
        if(!node) continue
        result.push(node.val)
        stack.push(node.right) 
        stack.push(node.left)
    }
    return result
};


// 迭代，入栈拦截
var preorderTraversal = function(root) {
    const result = [], stack = []
    if(!root) return result
    // 处理中结点，入栈：右、左
    stack.push(root)
    while(stack.length) {
        const node = stack.pop()
        result.push(node.val)
        if(node.right) stack.push(node.right) 
        if(node.left) stack.push(node.left)
    }
    return result
};

中序遍历

递归

/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal1 = function(root) {
    const result = []
    traverse(root)
    return result

    function traverse(node) {
        if(!node) return
        // 左、中、右
        traverse(node.left)
        result.push(node.val)
        traverse(node.right)
    }
};

迭代

// 迭代，中序遍历
var inorderTraversal = function(root) {
    const result = [], stack = []
    let p = root
    while(p || stack.length) {
        // 到最左边地下，然后用栈调右指针
        if(p) {
            // 左
            stack.push(p)
            p = p.left
        } else {
            // 中、右
            const node = stack.pop()
            result.push(node.val)
            p = node.right
        }
    }
    return result
};

后序遍历

递归

/**
 * 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 postorderTraversal1 = function(root) {
    const result = []
    traverse(root)
    return result

    function traverse(node) {
        if(!node) return
        // 左、右、中
        traverse(node.left)
        traverse(node.right)
        result.push(node.val)
    }
};

迭代

// 迭代，出栈处理拦截
var postorderTraversal2 = function(root) {
    const result = [], stack = []
    if(!root) return result
    // 处理中结点，入栈：左、右
    stack.push(root)
    while(stack.length) {
        const node = stack.pop()
        if(!node) continue
        result.push(node.val)
        stack.push(node.left)
        stack.push(node.right) 
    }
    return result.reverse()
};



var postorderTraversal = function(root) {
    const result = [], stack = []
    if(!root) return result
    // 处理中结点，入栈：左、右
    stack.push(root)
    while(stack.length) {
        const node = stack.pop()
        result.push(node.val)
        if(node.left) stack.push(node.left)
        if(node.right) stack.push(node.right) 
    }
    return result.reverse()
};

层次遍历

/**
 * 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 levelOrder = function(root) {
    const result = [], queue = []
    queue.push(root)
    if(!root) return result
    while(queue.length) {
        let length = queue.length
        let curLevel = []
        for(let i = 0; i < length; i++) {
            let node = queue.shift()
            curLevel.push(node.val)
            node.left && queue.push(node.left)
            node.right && queue.push(node.right)
        }
        result.push(curLevel)
    }
    return result
};

遍历总结

1. 前序遍历：
   1. 递归：处理中、左、右（递归）
   2. 迭代：处理中、右、左（入栈）
2. 中序遍历：
   1. 递归：左、处理中、右（递归）
   2. 迭代：比较复杂，使用指针总是找到左下角的节点，一路上入栈；找到后出栈处理中、右（指针）
3. 后序遍历：
   1. 递归：左、右、处理中
   2. 迭代：处理中、左、右（入栈），然后结果需要反转
4. 层次遍历：
   1. 按层次，比较有顺序