美文网首页
前端常见算法题(树篇)

前端常见算法题(树篇)

作者: 维李设论 | 来源:发表于2021-08-09 22:16 被阅读0次
    前端 | 前端常见算法题(树篇).png

    一、遍历问题

    2020.11.02

    No.94 二叉树的中序遍历

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

    示例:

    输入: [1,null,2,3]
    1

    2
    /
    3

    输出: [1,3,2]
    进阶: 递归算法很简单，你可以通过迭代算法完成吗？

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    方案一：

    /*
 * @lc app=leetcode.cn id=94 lang=javascript
 *
 * [94] 二叉树的中序遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    let r = [];
    // 递归函数
    const recurse = root => {
        // 递归终止条件
        if(!root) return;
        // 先遍历左子树
        recurse(root.left);
        // 遇到终止条件，此时的val是符合终止条件的值
        r.push(root.val);
        // 再遍历右子树
        recurse(root.right);
    };
    recurse(root);
    return r;
};

    方案二：

    /*
 * @lc app=leetcode.cn id=94 lang=javascript
 *
 * [94] 二叉树的中序遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    const res = [];
    const stk = [];
    while (root || stk.length) {
        while (root) {
            stk.push(root);
            root = root.left;
        }
        root = stk.pop();
        res.push(root.val);
        root = root.right;
    }
    return res;
};

    方案三：

    /*
 * @lc app=leetcode.cn id=94 lang=javascript
 *
 * [94] 二叉树的中序遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
    const res = [];
    let predecessor = null;

    while (root) {
        if (root.left) {
            // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
            predecessor = root.left;
            while (predecessor.right && predecessor.right !== root) {
                predecessor = predecessor.right;
            }

            // 让 predecessor 的右指针指向 root，继续遍历左子树
            if (!predecessor.right) {
                predecessor.right = root;
                root = root.left;
            }
            // 说明左子树已经访问完了，我们需要断开链接
            else {
                res.push(root.val);
                predecessor.right = null;
                root = root.right;
            }
        }
        // 如果没有左孩子，则直接访问右孩子
        else {
            res.push(root.val);
            root = root.right;
        }
    }

    return res;
};

    方案四：

    /*
 * @lc app=leetcode.cn id=94 lang=javascript
 *
 * [94] 二叉树的中序遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var inorderTraversal = function(root) {
  if (root) {
    return [...inorderTraversal(root.left), root.val, ...inorderTraversal(root.right)]
  } else {
    return []
  }
}

    有四种解法：1、利用递归来实现遍历，对于递归的终止条件要处理好，相当于是隐式的栈应用；2、利用栈来显式的执行，可以控制迭代和停止；3、Morris遍历算法：其本质是利用树种大量的null空间，利用线索树来实现链路的线索，该算法的核心是：当前节点记为cur，a、如果cur无左子节点，cur右移 cur = cur.right；b、如果有左子节点，找到cur左子树的最右节点，记为mostright，b1、如果mostright的right为null，让其指向cur，并且cur左移 cur = cur.left；b2、如果mostright的right指向cur，让其指为null，cur右移 cur = cur.right；4、利用js的...的iterable属性，可最简化写法

    2020.11.03

    No.102 二叉树的层序遍历

    给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

    示例：
    二叉树：[3,9,20,null,null,15,7],

    3

    /
    9 20
    /
    15 7
    返回其层次遍历结果：

    [
    [3],
    [9,20],
    [15,7]
    ]

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    方案一：

    /*
 * @lc app=leetcode.cn id=102 lang=javascript
 *
 * [102] 二叉树的层序遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
    const r = [];

    // 构造hash表
    let obj = {};

    // 递归循环 增加一个层级判断n
    const recurse = (curr, n) => {
       if(!curr) return;
       if(!obj[n]) {
        obj[n] = [curr.val]
       } else {
        obj[n].push(curr.val)
       }
       n++;
       recurse(curr.left, n);
       recurse(curr.right, n)
    }

    recurse(root, 0);

    for(let key in obj) {
        r.push(obj[key]);
    }
    
    return r;
};

    方案二：

    /*
 * @lc app=leetcode.cn id=102 lang=javascript
 *
 * [102] 二叉树的层序遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrder = function(root) {
  if (!root) return [];
  const items = []; // 存放所有节点
  const queue = [root, null]; // null 简化操作
  let levelNodes = []; // 存放每一层的节点

  while (queue.length > 0) {
    const t = queue.shift();

    if (t) {
      levelNodes.push(t.val)
      if (t.left) {
        queue.push(t.left);
      }
      if (t.right) {
        queue.push(t.right);
      }
    } else { // 一层已经遍历完了
      items.push(levelNodes);
      levelNodes = [];
      if (queue.length > 0) {
        queue.push(null)
      }
    }
  }

  return items;
};

    本题有两种思路：1、DFS：关键点在增加一个层级维度的判断，可以使用hash表或者队列等来实现；2、BFS：利用队列来优化循环的层数，从而实现广度优先搜索

    2020.11.04

    No.103 二叉树的锯齿形层次遍历

    给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

    例如：
    给定二叉树 [3,9,20,null,null,15,7],

    3

    /
    9 20
    /
    15 7
    返回锯齿形层次遍历如下：

    [
    [3],
    [20,9],
    [15,7]
    ]

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    方案一：

    /*
 * @lc app=leetcode.cn id=103 lang=javascript
 *
 * [103] 二叉树的锯齿形层次遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function(root) {
    const r = [];

    // 构造hash表
    let obj = {};

    const recurse = ( node, n ) => {
        if(!node) return;
        if( !obj[n] ) {
            obj[n] = [node.val];
        } else {
            obj[n].push(node.val)
        };
        n++;
        recurse(node.left, n);
        recurse(node.right, n);
    };

    recurse(root, 0);

    for(let key in obj) {
        // 偶数层从左向右，奇数层从右向左
        if( key % 2 == 0 ) {
            r.push(obj[key]);
        } else {
            r.push(obj[key].reverse());
        }
    }

    return r;
};

    方案二：

    /*
 * @lc app=leetcode.cn id=103 lang=javascript
 *
 * [103] 二叉树的锯齿形层次遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function (root) {
    let r = []
    let queen = []

    if (root) {
        queen.push([root, 0])
    }

    while (queen.length) {
        let [node, depth] = queen.shift()

        node.left && queen.push([node.left, depth + 1])
        node.right && queen.push([node.right, depth + 1])
        if (!r[depth]) {
            r[depth] = []
        }
        if (depth % 2 === 1) {
            r[depth].unshift(node.val)
        } else {
            r[depth].push(node.val)
        }
    }
    return r
};

    两种解法：1、DFS：只需将102层次遍历后的hash表中的key按奇偶要求进行输出即可；2、BFS：构造队列，同样对层次奇偶进行要求输出即可

    2020.11.05

    No.105 从前序与中序遍历序列构造二叉树

    根据一棵树的前序遍历与中序遍历构造二叉树。

    注意:
    你可以假设树中没有重复的元素。

    例如，给出

    前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]
    返回如下的二叉树：

    3

    /
    9 20
    /
    15 7

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    方案一：

    /*
 * @lc app=leetcode.cn id=105 lang=javascript
 *
 * [105] 从前序与中序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    // 递归终止条件
    if(inorder.length == 0) return null;
    // 根节点一定是前序遍历数组的第一个，在中序遍历数组中获取其位置，可以分离左子树和右子树
    const root = new TreeNode(preorder[0]),
        idx = inorder.indexOf(preorder[0]);
    
    root.left = buildTree(preorder.slice(1,idx+1), inorder.slice(0,idx));
    root.right = buildTree(preorder.slice(idx+1), inorder.slice(idx+1));
    return root;
};

    方案二：

    /*
 * @lc app=leetcode.cn id=105 lang=javascript
 *
 * [105] 从前序与中序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    pre = i = 0
    build = function(stop) {
        console.log(stop);
        if (inorder[i] != stop) {
            var root = new TreeNode(preorder[pre++])
            root.left = build(root.val)
            I++
            root.right = build(stop)
            return root
        }
        return null
    }
    return build()
};

    递归构建，有两种方法：1、利用slice切割根节点，递归，这样比较消耗性能，可以用map以及指针等优化处理；2、省去空间的消耗，这里利用一个停止位点进行每次迭代的输出，是generator函数的延展实现

    2020.11.06

    No.106 从中序与后序遍历序列构造二叉树

    根据一棵树的中序遍历与后序遍历构造二叉树。

    注意:
    你可以假设树中没有重复的元素。

    例如，给出

    中序遍历 inorder = [9,3,15,20,7]
    后序遍历 postorder = [9,15,7,20,3]
    返回如下的二叉树：

    3

    /
    9 20
    /
    15 7

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    方案一：

    /*
 * @lc app=leetcode.cn id=106 lang=javascript
 *
 * [106] 从中序与后序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    if( inorder.length == 0 ) return null;
    const root = new TreeNode(postorder[postorder.length - 1]),
        idx = inorder.indexOf(postorder[postorder.length-1]);
    root.left = buildTree(inorder.slice(0,idx), postorder.slice(0, idx));
    root.right = buildTree(inorder.slice(idx+1),postorder.slice(idx,postorder.length-1));
    return root;
};

    方案二：

    /*
 * @lc app=leetcode.cn id=106 lang=javascript
 *
 * [106] 从中序与后序遍历序列构造二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    let p = i = postorder.length - 1;
    let build = (stop) => {
        if(inorder[i] != stop) {
            let root = new TreeNode(postorder[p--])
            root.right = build(root.val)
            I--
            root.left = build(stop)
            return root
        }
        return null
    }
    return build()
};

    105题目变形，只需对后序倒序取根就可以分开左右子树

    2020.11.09

    No.107 二叉树的层次遍历-ii

    给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

    例如：
    给定二叉树 [3,9,20,null,null,15,7],

    3

    /
    9 20
    /
    15 7
    返回其自底向上的层次遍历为：

    [
    [15,7],
    [9,20],
    [3]
    ]

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    方案一：

    /*
 * @lc app=leetcode.cn id=107 lang=javascript
 *
 * [107] 二叉树的层次遍历 II
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
    const r = [];

    // 构造hash表
    let obj = {};

    const recurse = ( node, n ) => {
        if(!node) return;
        if(!obj[n]) {
            obj[n] = [node.val]
        } else {
            obj[n].push(node.val)
        };
        n++;
        recurse(node.left,n);
        recurse(node.right,n)
    };

    recurse(root, 0);

    for( let key in obj) {
        r.push(obj[key])
    };

    return r.reverse();
};

    方案二：

    /*
 * @lc app=leetcode.cn id=107 lang=javascript
 *
 * [107] 二叉树的层次遍历 II
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var levelOrderBottom = function(root) {
  if (!root) return [];
  const items = []; // 存放所有节点
  const queue = [root, null]; // null 简化操作
  let levelNodes = []; // 存放每一层的节点

  while (queue.length > 0) {
    const t = queue.shift();

    if (t) {
      levelNodes.push(t.val)
      if (t.left) {
        queue.push(t.left);
      }
      if (t.right) {
        queue.push(t.right);
      }
    } else { // 一层已经遍历完了
      items.push(levelNodes);
      levelNodes = [];
      if (queue.length > 0) {
        queue.push(null)
      }
    }
  }

  return items.reverse();
};

    思路和102题一样，只需要将结果反转即可

    2020.11.10

    No.144 二叉树的前序遍历

    给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

    示例 1：


    image

    相关文章

      网友评论

          本文标题：前端常见算法题(树篇)

          本文链接：https://www.haomeiwen.com/subject/edstbltx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|前端常见算法题(树篇)|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！