01递归遍历

1.递归遍历

前序遍历

题目

给你二叉树的根节点 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

进阶：递归算法很简单，你可以通过迭代算法完成吗？

思路

递归算法思路

确定递归函数的参数

确定递归函数的返回值

因为要打印出前序遍历节点的数值，所以参数里需要传入vector来放节点的数值，除了这一点就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是void

确定终止条件

在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return

确定单层递归的逻辑

前序遍历是中左右的顺序，所以在单层递归的逻辑，是要先取中节点的数值

TS实现


/**
 * 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[] {
    const result: number[] = [];
    if (root === null) return result;
    const traversal = (root: TreeNode, result: number[]) => {
        if (root === null) return;
        result.push(root.val);
        traversal(root.left, result);
        traversal(root.right, result);
    }
    
    traversal(root, result);

    return result;
};

中序遍历

题目

94. 二叉树的中序遍历思路

给定一个二叉树的根节点 root ，返回它的中序遍历。

示例 1：


输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：


输入：root = []
输出：[]

示例 3：


输入：root = [1]
输出：[1]

提示：

树中节点数目在范围 [0, 100] 内

100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路

递归算法思路

确定递归函数的参数

确定递归函数的返回值

因为要打印出前序遍历节点的数值，所以参数里需要传入vector来放节点的数值，除了这一点就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是void

确定终止条件

在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return

确定单层递归的逻辑

前序遍历是中左右的顺序，所以在单层递归的逻辑，是要先取中节点的数值

TS实现


/**
 * 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)
 *     }
 * }
 */

const traversal = (root: TreeNode, result: number[]) => {
    if (root === null) return;
    traversal(root.left, result);
    result.push(root.val);
    traversal(root.right, result);
}

function inorderTraversal(root: TreeNode | null): number[] {
    const result: number[] = [];
    traversal(root, result);
    return result;
};

后序遍历

题目

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

进阶：递归算法很简单，你可以通过迭代算法完成吗？

思路

递归算法思路

确定递归函数的参数

确定递归函数的返回值

因为要打印出前序遍历节点的数值，所以参数里需要传入vector来放节点的数值，除了这一点就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是void

确定终止条件

在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return

确定单层递归的逻辑

前序遍历是中左右的顺序，所以在单层递归的逻辑，是要先取中节点的数值

TS实现


/**
 * 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)
 *     }
 * }
 */

const traversal = (root: TreeNode, result: number[]) => {
    if (root === null) return;
    traversal(root.left, result);
    traversal(root.right, result);
    result.push(root.val);
}

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