前端 | 前端常见算法题(树篇).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