算法题练习——JS Node+python题解NC45 实现二叉树先序，中序和后序遍历

ゝ一世哀愁。 2024-04-07 11:52 57阅读 0赞

**描述**

> 给定一棵二叉树，分别按照二叉树先序，中序和后序打印所有的节点。

> 数据范围：0≤n≤1000，树上每个节点的val值满足 0≤val≤100
> 
> 要求：空间复杂度 O(n)，时间复杂度 O(n)

**样例解释：**

![c12d77bd170c44cda43d932fc1cfa8f7.png][]

> 如图二叉树结构

**示例1**

> 输入：\{1,2,3\}
> 
> 返回值：\[\[1,2,3\],\[2,1,3\],\[2,3,1\]\]
> 
> 说明：如题面图

**示例2**

> 输入：\{\}
> 
> 返回值：\[\[\],\[\],\[\]\]

**备注：**

> n≤10^6

**解析：**

> 既然题目中提到二叉树先序，中序，后序遍历，那么我们就先聊一聊关于一个二叉树的先序，中序，后序遍历。遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有节点，使每一个节点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
> 
> 二叉树的遍历主要有三种，括号内为其特点：
> 
>  *  先(根)序遍历（根左右）
>  *  中(根)序遍历（左根右）
>  *  后(根)序遍历（左右根）

**JavaScript Node题解：**

/*
     * function TreeNode(x) {
     *   this.val = x;
     *   this.left = null;
     *   this.right = null;
     * }
     */
    
    /**
     * 
     * @param root TreeNode类 the root of binary tree
     * @return int整型二维数组
     */
    let preArr = []
    let headArr = []
    let proArr = []
    function preOrders(root){
        if(!root) return null
        preArr.push(root.val)
        preOrders(root.left)
        preOrders(root.right)
    }
    function headOrders(root){
        if(!root) return null
        headOrders(root.left)
        headArr.push(root.val)
        headOrders(root.right)
    }
    function proOrders(root){
        if(!root) return null
        proOrders(root.left)
        proOrders(root.right)
        proArr.push(root.val)
    }
    function threeOrders( root ) {
        // write code here
        preOrders(root)
        headOrders(root)
        proOrders(root)
        let res = []
        res.push(preArr,headArr,proArr)
        return res
    }
    module.exports = {
        threeOrders : threeOrders
    };

**python代码解：**

# class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    #
    # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    #
    # 
    # @param root TreeNode类 the root of binary tree
    # @return int整型二维数组
    #
    class Solution:
        def threeOrders(self , root: TreeNode) -> List[List[int]]:
            # write code here
            self.res = [[],[],[]]
            self.dfs(root)
            return self.res
        def dfs(self,root):
            if not root: return
            self.res[0].append(root.val)
            self.dfs(root.left)
            self.res[1].append(root.val)
            self.dfs(root.right)
            self.res[2].append(root.val)
            return

[c12d77bd170c44cda43d932fc1cfa8f7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/fd5783f2d1db419eadb8dbefb45bfb1c.png