[面试 ] js 前序中序 后序

前序遍历

根节点=>左子树=>右子树
[面试 ] js 前序中序 后序
遍历顺序为ABC
[面试 ] js 前序中序 后序


代码:

var preorderTraversal = function(root) {
    let res = [];
    // 遍历函数
    function traversal(root) {
        if (root !== null) {
            // 访问根节点的值
            res.push(root.val);
            if (root.left) {
                // 递归遍历左子树
                traversal(root.left);
            };
            if (root.right) {
                // 递归遍历右子树
                traversal(root.right);
            };
        };
    };
    traversal(root);
    return res;
};

中序遍历

中序遍历满足左子树=>根节点=>右子树的顺序进行查询

[面试 ] js 前序中序 后序
当跑到到根节点B时,先得看看有没有左子树,正好有,所以先遍历了左子树A之后才是B,最后遍历右子树C,所以完整顺序顺序为ABC。

题目来自 leetcode94. 二叉树的中序遍历 ,描述如下:
[面试 ] js 前序中序 后序

var inorderTraversal = function(root) {
    let res = [];
    // 遍历函数
    function traversal(root) {
        if (root !== null) {
            if (root.left) {
                // 递归遍历左子树
                traversal(root.left);
            };
            // 访问根节点的值
            res.push(root.val);
            if (root.right) {
                // 递归遍历右子树
                traversal(root.right);
            };
        };
    };
    traversal(root);
    return res;
};

后序遍历

后序遍历满足左子树=>右子树=>根节点的顺序进行查询,还是从简单二叉树开始:
[面试 ] js 前序中序 后序

从根节点C出发,先访问左子树A,紧接着右子树B,最后根节点C,所以顺序为ABC。
题目来自leetcode145. 二叉树的后序遍历 ,题目描述如下:
[面试 ] js 前序中序 后序

var postorderTraversal = function(root) {
    let res = [];
    // 遍历函数
    function traversal(root) {
        if (root !== null) {
            if (root.left) {
                // 递归遍历左子树
                traversal(root.left);
            };
            if (root.right) {
                // 递归遍历右子树
                traversal(root.right);
            };
            // 访问根节点的值
            res.push(root.val);
        };
    };
    traversal(root);
    return res;
};

JS 前序遍历、中序遍历、后序遍历

上一篇:自从用了这款黑科技工具,妈妈再也不用担心我的c盘文件爆满了


下一篇:【Python】制作圆角图像的两种方案对比