【五月集训】第十九天打卡(二叉树)

144. 二叉树的前序遍历

题目链接

思路

根左右

题解

function preorderTraversal(root: TreeNode | null): number[] {
    let res = []
    function dfs(root: TreeNode | null) {
        if (root) {
            res.push(root.val)
            dfs(root.left)
            dfs(root.right)
        }
    }
    dfs(root)
    return res
};

144. 二叉树的中序遍历

题目链接

思路

左根右

题解

function inorderTraversal(root: TreeNode | null): number[] {
    let res = []
    function dfs(root: TreeNode | null) {
        if (root) {
            dfs(root.left)
            res.push(root.val)
            dfs(root.right)
        }
    }
    dfs(root)
    return res
};

144. 二叉树的后序遍历

题目链接

思路

左右根

题解

function postorderTraversal(root: TreeNode | null): number[] {
    let res = []
    function dfs(root: TreeNode | null) {
        if (root) {
            dfs(root.left)
            dfs(root.right)
            res.push(root.val)
        }
    }
    dfs(root)
    return res
};

104. 二叉树的最大深度

题目链接

思路

比较左子树的深度+1和右子树深度+1 取最大

题解

function maxDepth(root: TreeNode | null): number {
    if (!root) return 0
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
};