【leetcode】树形结构习题

二叉树的前序遍历
返回结果：[‘1’, ‘2’, ‘4’, ‘5’, ‘3’, ‘6’, ‘7’]
在这里插入图片描述
144.二叉树的前序遍历 - 迭代算法
给你二叉树的根节点 root ，返回它节点值的前序遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[1,2,4,5,6,7,3,8,9]
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
提示：
树中节点数目在范围 [0, 100] 内-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
 
function preorderTraversal(root: TreeNode | null): number[] {
    if (!root) return []
    let arr = []
    let stack = [root]
    while(stack.length) {
        let o = stack.pop()
        arr.push(o.val)
        o.right && stack.push(o.right)
        o.left && stack.push(o.left)
    }
    return arr
};

二叉树的中序遍历
返回结果：[‘4’, ‘2’, ‘5’, ‘1’, ‘6’, ‘3’, ‘7’]
在这里插入图片描述
94.二叉树的中序遍历
给定一个二叉树的根节点 root ，返回它的中序遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function inorderTraversal(root: TreeNode | null): number[] {
    let arr = []
    let stack = []
    let o = root
    while(stack.length || o) {
        while(o) {
            stack.push(o)
            o = o.left
        }
        let n = stack.pop()
        arr.push(n.val)
        o = n.right
    }
    return arr 
};

二叉树的后序遍历
返回结果：[‘4’, ‘5’, ‘2’, ‘6’, ‘7’, ‘3’, ‘1’]
在这里插入图片描述
145.二叉树的后序遍历
给你一棵二叉树的根节点 root ，返回其节点值的后序遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[3,2,1]
示例 2：
输入：root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出：[4,6,7,5,2,9,8,3,1]
示例 3：
输入：root = []
输出：[]
示例 4：
输入：root = [1]
输出：[1]
提示：
树中节点的数目在范围 [0, 100] 内-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function postorderTraversal(root: TreeNode | null): number[] {
    if (!root) return []
    let arr = []
    let stack = [root]
    while(stack.length) {
        let o = stack.pop()
        arr.unshift(o.val)
        o.left && stack.push(o.left)
        o.right && stack.push(o.right)
    }
    return arr
};

111.二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
提示：
树中节点数的范围在 [0, 105] 内-1000 <= Node.val <= 1000

/**
 * 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 minDepth = function(root) {
    if (!root) return 0
    let stack = [[root,1]]
    while( stack.length ) {
        let [o,n] = stack.shift()
        if (!o.left && !o.right) {
            return n
        }
        if (o.left) stack.push([o.left, n+1])
        if (o.right) stack.push([o.right, n+1])
    }
};

104.二叉树的最大深度
给定一个二叉树 root ，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：3
示例 2：
输入：root = [1,null,2]
输出：2
提示：
树中节点的数量在 [0, 104] 区间内。-100 <= Node.val <= 100

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function maxDepth(root: TreeNode | null): number {
    if (!root) return 0
    let stack = [root]
    let num = 0
    while(stack.length) {
        let len = stack.length
        num++
        while(len--) {
            let o = stack.shift()
            o.left && stack.push(o.left)
            o.right && stack.push(o.right)
        }
    }
    return num
};

226.翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：
输入：root = []
输出：[]
提示：
树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function invertTree(root: TreeNode | null): TreeNode | null {
    if (root === null) return null

    let tmp = root.left
    root.left = root.right
    root.right = tmp
    
    invertTree(root.left)
    invertTree(root.right)

    return root
};

100.相同的树
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false
示例 3
输入：p = [1,2,1], q = [1,1,2]
输出：false
提示：
两棵树上的节点数目都在范围 [0, 100] 内
-104 <= Node.val <= 104

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
    if (p === null && q === null) return true
    if (p === null || q === null) return false
    if (p.val !== q.val) return false

    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
};