深度优先遍历

前序遍历

根左右

function preorderTraversal(root: TreeNode | null): number[] {
        // 栈实现
    const ans: number[] = []
    if(!root){
        return ans
    }
    const stk:TreeNode[] = [root] // 将节点 压入栈内
    while(stk.length){
        // 若栈不为空，每次从栈中弹出一个节点 处理该节点
        const {left,right,val} = stk.pop()
        // 压入根节点
        ans.push(val)
        // 先把节点右孩子压入栈，接着把节点左孩子压入栈（如果有孩子节点）
        right && stk.push(right)
        left && stk.push(left)
    }
    return ans
};

中序遍历

左根右

递归实现

function inorderTraversal(root: TreeNode | null): number[] {
    // 递归实现
    const ans: number[] = []
    const dfs = (root: TreeNode) => {
        if(!root){
            return;
        }

        dfs(root.left)
        ans.push(root.val)
        dfs(root.right)
    }
    dfs(root)

    return ans
};

栈实现

function inorderTraversal(root: TreeNode | null): number[] {
    // 栈实现
    const ans: number[] = []
    let stk: TreeNode[] = [] // 初始化
    while(root || stk.length > 0){
        if(root){
            stk.push(root);
            root = root.left; // 左节点依次入栈
        }else {
            // 左节点为空时弹出 处理
            root = stk.pop();
            ans.push(root.val);
            root = root.right;
        }

    }
    return ans
};

后续遍历

左右根

递归实现

function postorderTraversal(root: TreeNode | null): number[] {
    // 递归 
    // 后续遍历 我们先递归左右子树，然后再访问根节点。

    const ans: number[] = []
    const dfs = (root: TreeNode | null) => {
        if(!root){
            return;
        }

        dfs(root.left)
        dfs(root.right)
        ans.push(root.val)
    }

    dfs(root)
    return ans
};

栈实现

计算根左右的结果，再利用reverse反转得到后续遍历的结果

function postorderTraversal(root: TreeNode | null): number[] {
    // 栈实现
    const ans: number[] = []
    if(!root){
        return ans
    }

    const stk:TreeNode[] = [root] // 将节点 压入栈内
    while(stk.length){
        // 若栈不为空，每次从栈中弹出一个节点 处理该节点
        const {left,right,val} = stk.pop()
        console.log('val',val)
        ans.push(val)
        // 先把节点左孩子压入栈，接着把节点右孩子压入栈（如果有孩子节点）
        left && stk.push(left)
        right && stk.push(right)
    }

    // 反转 得到后序遍历结果
    ans.reverse();
    return ans
};