二叉树

!! 不要在一开始就纠结细节； 涉及父问题跟子问题是相似的，就适合用递归实现；

递：一直到边界条件 归：一路回去

104. 二叉树的最大深度

function maxDepth(root: TreeNode | null): number {
    if(!root) return 0

    let left = maxDepth(root.left);
    let right = maxDepth(root.right);

    return Math.max(left,right)+1
};

通过全局变量来存，遍历完这个树，它就是答案了；

function maxDepth(root: TreeNode | null): number {
    if(!root) return 0;

    let ans = 0;
    const f = (node, cnt)=>{
        if(!node) return;
        cnt +=1
        ans = Math.max(ans,cnt)
        f(node.left, cnt);
        f(node.right, cnt);
    }
    f(root,0)
    return ans;
};

二叉树的遍历：

144. 二叉树的前序遍历94. 二叉树的中序遍历145. 二叉树的后序遍历

递归直接写了就完了；

function postorderTraversal(root: TreeNode | null): number[] {
    let arr:number[] = [];
    traversal(root, arr);
    return arr;
};

const traversal = (cur: TreeNode | null, arr:number[])=>{
    if(!cur) return;
    traversal(cur.left, arr);
    traversal(cur.right, arr);
    arr.push(cur.val)
}

左右视图

199.二叉树的右视图

二叉树的右视图：

• 对于递归，先遍历右子树，然后在遍历深度等于目前答案长度的时候，记录答案；永远右子树优先；

function rightSideView(root: TreeNode | null): number[] {
    if(!root) return [];
    let ans:number[] = [];

    const dfs = (node, depth)=>{
        if(!node) return;
        if(ans.length===depth){
            ans.push(node.val)
        }

        dfs(node.right, depth+1);
        dfs(node.left, depth+1);
    }
    dfs(root, 0);
    return ans;
};

• 对于层序遍历，右视图是每层的最后一个节点；左视图是每层第一个节点；

右视图：

function rightSideView(root: TreeNode | null): number[] {
    if(!root) return [];
    let stack:TreeNode[] = [];
    let ans:number[] = [];

    stack.push(root);

    while(stack.length>0){

        let len = stack.length;

        for(let i=0;i<len;i++){
            let node = stack.shift()! // 取，并且从数组中删除
            if(i===len-1){
                ans.push(node.val)
            }

            if(node.left !== null){
                stack.push(node.left);
            }
            if(node.right !== null){
                stack.push(node.right);
            }
        }
    }
    return ans;
};

左视图：

右视图：

function rightSideView(root: TreeNode | null): number[] {
    if(!root) return [];
    let stack:TreeNode[] = [];
    let ans:number[] = [];

    stack.push(root);

    while(stack.length>0){

        let len = stack.length;

        for(let i=0;i<len;i++){
            let node = stack.shift()! // 取，并且从数组中删除
            if(i===0){  // 稍微修改右视图即可；
                ans.push(node.val)
            }

            if(node.left !== null){
                stack.push(node.left);
            }
            if(node.right !== null){
                stack.push(node.right);
            }
        }
    }
    return ans;
};