关于leetcode算法:前端常见算法题树篇

47次阅读

共计 46613 个字符，预计需要花费 117 分钟才能阅读完成。

遍历问题

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：

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

输出：root = []
输入：[]
示例 3：

输出：root = [1]
输入：[1]
示例 4：

输出：root = [1,2]
输入：[1,2]
示例 5：

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

提醒：

树中节点数目在范畴 [0, 100] 内
-100 <= Node.val <= 100
 

进阶：递归算法很简略，你能够通过迭代算法实现吗？

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划一：
/*
 * @lc app=leetcode.cn id=144 lang=javascript
 *
 * [144] 二叉树的前序遍历
 */

// @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 preorderTraversal = function(root) {const r = [];

    const recurse = node => {if(!node) return;
        r.push(node.val);
        node.left && recurse(node.left);
        node.right && recurse(node.right)
    };

    recurse(root);

    return r;
};
计划二：
/*
 * @lc app=leetcode.cn id=144 lang=javascript
 *
 * [144] 二叉树的前序遍历
 */

// @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 preorderTraversal = function(root) {if(!root) return [];
    const r = [],
          stack = [root];

    while(stack.length > 0) {const node = stack.pop()
        r.push(node.val);
        // 结构栈，入栈须要先进入右节点，再进入左节点，出栈时能力先左后右
        node.right && stack.push(node.right);
        node.left && stack.push(node.left)
    }

    return r;
};
计划三：
/*
 * @lc app=leetcode.cn id=144 lang=javascript
 *
 * [144] 二叉树的前序遍历
 */

// @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 preorderTraversal = 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;
                res.push(root.val);
                root = root.left;
            }
            // 阐明左子树曾经拜访完了，咱们须要断开链接
            else {
                predecessor.right = null;
                root = root.right;
            }
        }
        // 如果没有左孩子，则间接拜访右孩子
        else {res.push(root.val);
            root = root.right;
        }
    }

    return res;
};
计划四：
/*
 * @lc app=leetcode.cn id=144 lang=javascript
 *
 * [144] 二叉树的前序遍历
 */

// @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 preorderTraversal = function(root) {if (root) {return [ root.val, ...preorderTraversal(root.left), ...preorderTraversal(root.right) ]
    } else {return []
    }
};

同 94 的中序遍历的四种计划：1、递归；2、栈优化；3、Morris 算法；4、js 的 … 迭代

2020.11.11

No.145 二叉树的后序遍历

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

示例:

输出: [1,null,2,3]  
  1
   \
    2
   /
  3

输入: [3,2,1]
进阶: 递归算法很简略，你能够通过迭代算法实现吗？

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划一：
/*
 * @lc app=leetcode.cn id=145 lang=javascript
 *
 * [145] 二叉树的后序遍历
 */

// @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 postorderTraversal = function(root) {const r = [];

    const recurse = node => {if(!node) return;

        node.left && recurse(node.left);
        node.right && recurse(node.right);
        r.push(node.val);
    }

    recurse(root);

    return r;
};
计划二：
/*
 * @lc app=leetcode.cn id=145 lang=javascript
 *
 * [145] 二叉树的后序遍历
 */

// @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 postorderTraversal = function(root) {if(!root) return [];
    const r = [],
          stack = [root];

    while(stack.length > 0) {let node = stack.pop();
        node.left && stack.push(node.left);
        node.right && stack.push(node.right);
        r.unshift(node.val);
    }      

    return r;
};
计划三：
/*
 * @lc app=leetcode.cn id=145 lang=javascript
 *
 * [145] 二叉树的后序遍历
 */

// @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 postorderTraversal = function(root) {const res = [];
    let predecessor = null;

    while (root) {if (root.right) {
            // predecessor 节点就是以后 root 节点向左走一步，而后始终向右走至无奈走为止
            predecessor = root.right;
            while (predecessor.left && predecessor.left !== root) {predecessor = predecessor.left;}

            // 让 predecessor 的右指针指向 root，持续遍历左子树
            if (!predecessor.left) {
                predecessor.left = root;
                res.unshift(root.val);
                root = root.right;
            }
            // 阐明左子树曾经拜访完了，咱们须要断开链接
            else {
                predecessor.left = null;
                root = root.left;
            }
        }
        // 如果没有左孩子，则间接拜访右孩子
        else {res.unshift(root.val);
            root = root.left;
        }
    }

    return res;
};
计划四：
/*
 * @lc app=leetcode.cn id=145 lang=javascript
 *
 * [145] 二叉树的后序遍历
 */

// @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 postorderTraversal = function(root) {if (root) {return [ ...postorderTraversal(root.left), ...postorderTraversal(root.right), root.val]
    } else {return []
    }
};

同 144 前序遍历，有四种解法：1、递归；2、栈；3、Morris 算法；4、… 开展符

2020.11.12

No.1008 前序遍历结构二叉搜寻树

返回与给定前序遍历 preorder 相匹配的二叉搜寻树（binary search tree）的根结点。

(回忆一下，二叉搜寻树是二叉树的一种，其每个节点都满足以下规定，对于 node.left 的任何后辈，值总 < node.val，而 node.right 的任何后辈，值总 > node.val。此外，前序遍历首先显示节点 node 的值，而后遍历 node.left，接着遍历 node.right。）

题目保障，对于给定的测试用例，总能找到满足要求的二叉搜寻树。

 

示例：

输出：[8,5,1,7,10,12]
输入：[8,5,10,1,7,null,12]

 

提醒：

1 <= preorder.length <= 100
1 <= preorder[i] <= 10^8
preorder 中的值互不雷同

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/construct-binary-search-tree-from-preorder-traversal
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划一：
/*
 * @lc app=leetcode.cn id=1008 lang=javascript
 *
 * [1008] 前序遍历结构二叉搜寻树
 */

// @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 {number[]} preorder
 * @return {TreeNode}
 */
var bstFromPreorder = function(preorder) {if(preorder.length == 0) return null;

    const root = preorder.shift();

    let node = new TreeNode(root);

    node.left = bstFromPreorder(preorder.filter(item => item <= root));
    node.right = bstFromPreorder(preorder.filter(item => item > root))
    
    return node;
};
计划二：
/*
 * @lc app=leetcode.cn id=1008 lang=javascript
 *
 * [1008] 前序遍历结构二叉搜寻树
 */

// @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 {number[]} preorder
 * @return {TreeNode}
 */
var bstFromPreorder = function(preorder) {if(preorder.length == 0) return null;

    let root = new TreeNode(preorder[0]),
        stack = [root],
        curr,
        child;

    
    for(let i = 1; i < preorder.length; i++) {child = new TreeNode(preorder[i]);
        curr = stack[0];
        while(stack.length != 0 && stack[0].val < child.val ) {curr = stack.shift();
        }
        curr.val > child.val ? curr.left = child : curr.right = child;
        stack.unshift(child);
    }

    return root;
};

两种解法：1、递归，对于根的左右要求进行拆散；2、应用栈优化计划 1 中的递归

总结：
  1. 和问题常见的做法次要是利用 map、hash、栈型等数据结构来进行优化解决，其次是利用左右指针的归约来进行循环的次数；
  2. 对于子问题常见的解法是利用动静布局及回溯剪枝来解决优化

二叉搜寻树问题

2020.11.13

No.95 不同的二叉搜寻树 -ii

给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜寻树。

 

示例：

输出：3
输入：
[
 [1,null,3,2],
 [3,2,null,1],
 [3,1,null,null,2],
 [2,1,3],
 [1,null,2,null,3]
]
解释：
以上的输入对应以下 5 种不同构造的二叉搜寻树：

  1         3     3      2      1
   \       /     /      / \      \
    3     2     1      1   3      2
   /     /       \                 \
  2     1         2                 3
 

提醒：

0 <= n <= 8

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees-ii
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划：
/*
 * @lc app=leetcode.cn id=95 lang=javascript
 *
 * [95] 不同的二叉搜寻树 II
 */

// @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 {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function(n) {
    // 后果个数合乎卡特兰数字
    if(n == 0) return [];
    
    // 递归构建树
    const buildTree = (start, end) => {let r = [];
        // 递归终止条件
        if(start > end) return [null];

        for(let i = start; i <= end; i++) {
            // 以 i 为核心分成左右两边
            let left = buildTree(start, i-1),
                right = buildTree(i+1, end);
            
            for(const leftNode of left) {for( const rightNode of right) {let node = new TreeNode(i);
                    node.left = leftNode;
                    node.right = rightNode;
                    r.push(node)
                }
            }
        }

        return r;
    }

    return buildTree(1, n);
    
};

次要是递归解决：按根节点拆散左右子节点，而后递归生成树，再拼接到根节点上

2020.11.16

No.96 不同的二叉搜寻树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜寻树有多少种？

示例:

输出: 3
输入: 5
解释:
给定 n = 3, 一共有 5 种不同构造的二叉搜寻树:

  1         3     3      2      1
   \       /     /      / \      \
    3     2     1      1   3      2
   /     /       \                 \
  2     1         2                 3

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划一：
/*
 * @lc app=leetcode.cn id=96 lang=javascript
 *
 * [96] 不同的二叉搜寻树
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {// 后果合乎卡特兰数 ( 1 / n+1) * C(2n,n) => (1 / n+1)*(2n! / n! * n!)

    const fac = m => {
        let f = 1;
        while(m > 0) {
            f*=m;
            m--;
        }
        return f;
    };

    return (1 / ( n + 1) ) * fac(2*n) / (fac(n) * fac (n) )
};
计划二：
/*
 * @lc app=leetcode.cn id=96 lang=javascript
 *
 * [96] 不同的二叉搜寻树
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {if(n===1||n===0) return 1;
    var res=0;
    for(var i=1;i<=n;i++){res += numTrees(i-1) * numTrees(n-i);
    }
    return res;
};
计划三：
/*
 * @lc app=leetcode.cn id=96 lang=javascript
 *
 * [96] 不同的二叉搜寻树
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {var dp= new Array(n+1).fill(0);
    dp[0]=1;
    dp[1]=1;
    for(var i=2;i<=n;i++){for(var j=1;j<=i;j++){dp[i] += dp[j-1]*dp[(i-j)];
        }
    }
    return dp[n];
};

有三种解法：1、数学方法：后果合乎卡特兰数，应用卡特兰数的通项公式解决，(1/n+1)*C2nn；2、递归；3、动静布局

2020.11.17

No.98 验证二叉搜寻树

给定一个二叉树，判断其是否是一个无效的二叉搜寻树。

假如一个二叉搜寻树具备如下特色：

节点的左子树只蕴含小于以后节点的数。
节点的右子树只蕴含大于以后节点的数。
所有左子树和右子树本身必须也是二叉搜寻树。
示例 1:

输出:
   2
  / \
 1   3
输入: true
示例 2:

输出:
   5
  / \
 1   4
    / \
   3   6
输入: false
解释: 输出为: [5,1,4,null,null,3,6]。
    根节点的值为 5，然而其右子节点值为 4。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划一：
/*
 * @lc app=leetcode.cn id=98 lang=javascript
 *
 * [98] 验证二叉搜寻树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    // 中序遍历
    const inorderTraversal = root => {const r = [];

        const recurse = root => {if(!root) return;
            recurse(root.left);
            r.push(root.val);
            recurse(root.right);
        }
            
        recurse(root);

        return r;
    }

    // 判断是否升序
    const isAsec = arr => {for(let p1=0,p2=1;p2<arr.length;p1++,p2++) {if(arr[p1]>=arr[p2]) return false;
        }
        return true;
    }

    return isAsec(inorderTraversal(root));
};
计划二：
/*
 * @lc app=leetcode.cn id=98 lang=javascript
 *
 * [98] 验证二叉搜寻树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
      // 递归
      const helper = (root, lower, upper) => {if (root === null) {return true;}
        if (root.val <= lower || root.val >= upper) {return false;}
        return helper(root.left, lower, root.val) && helper(root.right, root.val, upper);
    }
    return helper(root, -Infinity, Infinity);
};

有两种解法：1、利用中序遍历为升序的特点，结构中序遍历，判断是否升序；2、递归

2020.11.18

No.99 复原二叉搜寻树

给你二叉搜寻树的根节点 root，该树中的两个节点被谬误地替换。请在不扭转其构造的状况下，复原这棵树。

进阶：应用 O(n) 空间复杂度的解法很容易实现。你能想出一个只应用常数空间的解决方案吗？

 

示例 1：

输出：root = [1,3,null,null,2]
输入：[3,1,null,null,2]
解释：3 不能是 1 左孩子，因为 3 > 1。替换 1 和 3 使二叉搜寻树无效。
示例 2：

输出：root = [3,1,4,null,null,2]
输入：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3。替换 2 和 3 使二叉搜寻树无效。
 

提醒：

树上节点的数目在范畴 [2, 1000] 内
-231 <= Node.val <= 231 – 1

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/recover-binary-search-tree
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划一：
/*
 * @lc app=leetcode.cn id=99 lang=javascript
 *
 * [99] 复原二叉搜寻树
 */

// @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 {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {
    // 1 将错位的二叉搜寻树中序遍历，确定谬误位点
    // 1.1 中序遍历 
    const inorderTraversal = root => {const r = [];

        const recurse = root => {if(!root) return;
            recurse(root.left);
            r.push(root.val);
            recurse(root.right);
        }
            
        recurse(root);

        return r;
    }
    // 1.2 获取替换地位
    const replaceIdx = arr => {const _arr = arr.slice().sort((a,b)=>a-b);

        let r = [];
        for(let i=0;i<arr.length;i++) {if(arr[i] != _arr[i]) {r.push( arr[i] )
            }
        };

        return r;
    }

    // 2 替换谬误位点
    const swapRoot = (root, count, x, y) => {if(root) {if(root.val == x || root.val == y) {
                root.val = root.val == x ? y : x;
                if(--count == 0) return;
            }
            swapRoot(root.left, count, x, y);
            swapRoot(root.right, count, x, y);
        }
    }

    const [x,y] = replaceIdx(inorderTraversal(root)).slice(0,2);

    swapRoot(root,2,x,y);
};
计划二：
/*
 * @lc app=leetcode.cn id=99 lang=javascript
 *
 * [99] 复原二叉搜寻树
 */

// @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 {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {const swap = (x, y) => {
        const temp = x.val;
        x.val = y.val;
        y.val = temp;
    }
    const stack = [];
    let x = null, y = null, pred = null;

    while (stack.length || root !== null) {while (root !== null) {stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      if (pred !== null && root.val < pred.val) {
        y = root;
        if (x === null) {x = pred;}
        else break;
      }
      pred = root;
      root = root.right;
    }
    swap(x, y);
};
计划三：
/*
 * @lc app=leetcode.cn id=99 lang=javascript
 *
 * [99] 复原二叉搜寻树
 */

// @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 {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {const swap = (x, y) => {
        const temp = x.val;
        x.val = y.val;
        y.val = temp;
    }
      
    let x = null, y = null, pred = null, predecessor = null;

    while (root !== null) {if (root.left !== null) {
        // predecessor 节点就是以后 root 节点向左走一步，而后始终向右走至无奈走为止
        predecessor = root.left;
        while (predecessor.right !== null && predecessor.right !== root)
          predecessor = predecessor.right;

        // 让 predecessor 的右指针指向 root，持续遍历左子树
        if (predecessor.right === null) {
          predecessor.right = root;
          root = root.left;
        }
        // 阐明左子树曾经拜访完了，咱们须要断开链接
        else {if (pred !== null && root.val < pred.val) {
            y = root;
            if (x === null) {x = pred;}
          }
          pred = root;

          predecessor.right = null;
          root = root.right;
        }
      }
      // 如果没有左孩子，则间接拜访右孩子
      else {if (pred !== null && root.val < pred.val) {
            y = root;
            if (x === null) {x = pred;}
        }
        pred = root;

        root = root.right;
      }
    }
    swap(x, y);
};

整体思路同 98 题的第一种计划，都是利用中序遍历为升序来获取谬误位点，本题 hard 次要在于对空间复杂度的优化，有三种计划：1、利用数组去查找谬误位点；2、利用一个 pred 的地位，只有获取到不雷同就能够进行，不须要齐全遍历完数组，相当于隐式的数组；3、Morris 算法，能够将空间复杂度降为常数级别

2020.11.19

No.173 二叉搜寻树迭代器

实现一个二叉搜寻树迭代器。你将应用二叉搜寻树的根节点初始化迭代器。

调用 next() 将返回二叉搜寻树中的下一个最小的数。

 

示例：

BSTIterator iterator = new BSTIterator(root);
iterator.next();    // 返回 3
iterator.next();    // 返回 7
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 9
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 15
iterator.hasNext(); // 返回 true
iterator.next();    // 返回 20
iterator.hasNext(); // 返回 false
 

提醒：

next() 和 hasNext() 操作的工夫复杂度是 O(1)，并应用 O(h) 内存，其中 h 是树的高度。
你能够假如 next() 调用总是无效的，也就是说，当调用 next() 时，BST 中至多存在一个下一个最小的数。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search-tree-iterator
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划一：
/*
 * @lc app=leetcode.cn id=173 lang=javascript
 *
 * [173] 二叉搜寻树迭代器
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 */
var BSTIterator = function(root) {
    // 中序遍历
    const inorderTraversal = root => {const r = [];

        const recurse = root => {if(!root) return;
            recurse(root.left);
            r.push(root.val);
            recurse(root.right);
        }
            
        recurse(root);

        return r;
    };
    
    /**
     * 其实返回一个对象就行了，这里用到了 js 的原型链机制
     * {
        arr: arr, 
        i: 0,
        next: function() {let hasNext = this.hasNext(),
                next = hasNext ? this.arr[this.i++] : undefined;
            
            return next;
        },
        hasNext: function() {return this.i < this.arr.length;}
     * }
     */

    // 挂到 this 上
    this.arr = inorderTraversal(root);
    this.i = 0;
};

/**
 * @return the next smallest number
 * @return {number}
 */
BSTIterator.prototype.next = function() {let hasNext = this.hasNext(),
        next = hasNext ? this.arr[this.i++] : undefined;
    
    return next;
};

/**
 * @return whether we have a next smallest number
 * @return {boolean}
 */
BSTIterator.prototype.hasNext = function() {return this.i < this.arr.length;};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * var obj = new BSTIterator(root)
 * var param_1 = obj.next()
 * var param_2 = obj.hasNext()
 */
计划二：
/*
 * @lc app=leetcode.cn id=173 lang=javascript
 *
 * [173] 二叉搜寻树迭代器
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 */
var BSTIterator = function(root) {let gen = function* () {let stack = [];
        let node = root;
        while (node || stack.length) {while (node) {stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            yield node.val;
            node = node.right;
        }
    }
    this.gen = gen();
    this.cursor = this.gen.next();};

/**
 * @return the next smallest number
 * @return {number}
 */
BSTIterator.prototype.next = function() {
    let value = this.cursor.value;
    this.cursor = this.gen.next();
    return value;
};

/**
 * @return whether we have a next smallest number
 * @return {boolean}
 */
BSTIterator.prototype.hasNext = function() {return !this.cursor.done;};

/**
 * Your BSTIterator object will be instantiated and called as such:
 * var obj = new BSTIterator(root)
 * var param_1 = obj.next()
 * var param_2 = obj.hasNext()
 */

整体思路就是先获取中序遍历，中序遍历能够有不同的优化，而后实现迭代器，这里有两种计划：1、利用 js 的原型链机制；2、利用 js 的 es6 曾经实现的生成器

2020.11.20

No.230 二叉搜寻树中第 k 小的元素

给定一个二叉搜寻树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

阐明：
你能够假如 k 总是无效的，1 ≤ k ≤ 二叉搜寻树元素个数。

示例 1:

输出: root = [3,1,4,null,2], k = 1
  3
 / \
1   4
 \
  2
输入: 1
示例 2:

输出: root = [5,3,6,2,4,null,null,1], k = 3
      5
     / \
    3   6
   / \
  2   4
 /
1
输入: 3
进阶：
如果二叉搜寻树常常被批改（插入 / 删除操作）并且你须要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划：
/*
 * @lc app=leetcode.cn id=230 lang=javascript
 *
 * [230] 二叉搜寻树中第 K 小的元素
 */

// @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
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    // 中序遍历
    const inorderTraversal = root => {const r = [];

        const recurse = root => {
            // 这里对 r 的长度进行判断剪枝优化
            if(!root || r.length >= k) return;
            recurse(root.left);
            r.push(root.val);
            recurse(root.right);
        }
            
        recurse(root);

        return r;
    };

    return inorderTraversal(root)[k-1]
};

利用中序遍历获取第 k - 1 个元素即可，求中序遍历的办法见 94 题，有四种计划，因为会频繁批改树，因此这里能够依据获取数组长度等进行优化

2020.11.23

No.235 二叉搜寻树的最近公共先人

给定一个二叉搜寻树, 找到该树中两个指定节点的最近公共先人。

百度百科中最近公共先人的定义为：“对于有根树 T 的两个结点 p、q，最近公共先人示意为一个结点 x，满足 x 是 p、q 的先人且 x 的深度尽可能大（一个节点也能够是它本人的先人）。”

例如，给定如下二叉搜寻树:  root = [6,2,8,0,4,7,9,null,null,3,5]

示例 1:

输出: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输入: 6
解释: 节点 2 和节点 8 的最近公共先人是 6。
示例 2:

输出: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输入: 2
解释: 节点 2 和节点 4 的最近公共先人是 2, 因为依据定义最近公共先人节点能够为节点自身。
 

阐明:

所有节点的值都是惟一的。
p、q 为不同节点且均存在于给定的二叉搜寻树中。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划一：
/*
 * @lc app=leetcode.cn id=235 lang=javascript
 *
 * [235] 二叉搜寻树的最近公共先人
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    // 获取门路，返回一个数组链表
    const bstPath = (root, val) => {const r = [];
        // 递归
        const recurse = node => {if(!node) return;
            const v = node.val;
            r.unshift(v);
            if(val > v) {recurse(node.right);
            } else if (val < v) {recurse(node.left);
            } else {return;}
        };

        recurse(root);

        return r;
    };

    // 依据门路数组，返回两数组最近公共先人
    const lowestCommonValue = (arr1, arr2) => {
        let s,l;
        if(arr1.length <= arr2.length) {
            s = arr1;
            l = arr2;
        } else {
            s = arr2;
            l = arr1;
        }

        for(let i=0; i<s.length; i++) {if(l.indexOf(s[i]) != -1) {return s[i];
            }
        }
    };

    return {val: lowestCommonValue( bstPath(root,p.val), bstPath(root,q.val) )};
};
计划二：
/*
 * @lc app=leetcode.cn id=235 lang=javascript
 *
 * [235] 二叉搜寻树的最近公共先人
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
const lowestCommonAncestor = (root, p, q) => {if (p.val < root.val && q.val < root.val) {return lowestCommonAncestor(root.left, p, q);
  }
  if (p.val > root.val && q.val > root.val) {return lowestCommonAncestor(root.right, p, q);
  }
  return root;
};
计划三：
/*
 * @lc app=leetcode.cn id=235 lang=javascript
 *
 * [235] 二叉搜寻树的最近公共先人
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
const lowestCommonAncestor = (root, p, q) => {while (root) {if (p.val < root.val && q.val < root.val) {root = root.left;} else if (p.val > root.val && q.val > root.val) {root = root.right;} else {break;}
  }
  return root;
};

有三种解法：1、结构门路链表构造，获取数组链表的最近公共节点；2、递归；3、迭代

2020.11.24

No.501 二叉搜寻树中的众数

给定一个有雷同值的二叉搜寻树（BST），找出 BST 中的所有众数（呈现频率最高的元素）。

假设 BST 有如下定义：

结点左子树中所含结点的值小于等于以后结点的值
结点右子树中所含结点的值大于等于以后结点的值
左子树和右子树都是二叉搜寻树
例如：
给定 BST [1,null,2,2],

  1
   \
    2
   /
  2
返回[2].

提醒：如果众数超过 1 个，不需思考输入程序

进阶：你能够不应用额定的空间吗？（假如由递归产生的隐式调用栈的开销不被计算在内）

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划一：
/*
 * @lc app=leetcode.cn id=501 lang=javascript
 *
 * [501] 二叉搜寻树中的众数
 */

// @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 findMode = function(root) {
    // 结构 hash 表
    const obj = {};
    const recurse = node => {if(!node) return;
        if(obj[node.val]) {obj[node.val]++;
        } else {obj[node.val] = 1;
        }
        node.left && recurse(node.left);
        node.right && recurse(node.right);
    }
    recurse(root);
    // 获取 value 的最大值
    let max = Math.max(...Object.values(obj));
    // 对 hash 表遍历，获取对应最大值的 key
    const r = [];
    for(let key in obj) {if(obj[key] == max) r.push(key);
    }
    return r;
};
计划二：
/*
 * @lc app=leetcode.cn id=501 lang=javascript
 *
 * [501] 二叉搜寻树中的众数
 */

// @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 findMode = function(root) {
    let base = 0, count = 0, maxCount = 0;
    let answer = [];

    const update = (x) => {if (x === base) {++count;} else {
            count = 1;
            base = x;
        }
        if (count === maxCount) {answer.push(base);
        }
        if (count > maxCount) {
            maxCount = count;
            answer = [base];
        }
    }

    const dfs = (o) => {if (!o) {return;}
        dfs(o.left);
        update(o.val);
        dfs(o.right);
    }

    dfs(root);
    return answer;
};
计划三：
/*
 * @lc app=leetcode.cn id=501 lang=javascript
 *
 * [501] 二叉搜寻树中的众数
 */

// @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 findMode = function(root) {
    let base = 0, count = 0, maxCount = 0;
    let answer = [];

    const update = (x) => {if (x === base) {++count;} else {
            count = 1;
            base = x;
        }
        if (count === maxCount) {answer.push(base);
        }
        if (count > maxCount) {
            maxCount = count;
            answer = [base];
        }
    }

    let cur = root, pre = null;
    while (cur !== null) {if (cur.left === null) {update(cur.val);
            cur = cur.right;
            continue;
        }
        pre = cur.left;
        while (pre.right !== null && pre.right !== cur) {pre = pre.right;}
        if (pre.right === null) {
            pre.right = cur;
            cur = cur.left;
        } else {
            pre.right = null;
            update(cur.val);
            cur = cur.right;
        }
    }
    return answer;
};

有三种计划：1、最简略也是最好想的，利用 hash 表结构判断众数；2、计划 1 会额定利用 hash 表的空间，利用中序遍历能够应用几个指针来进行判断输入，空间复杂度为 O(n)；3、进一步优化计划 2，利用 Morris 算法优化中序遍历时的空间损耗，空间复杂度为 O(1)

2020.11.25

No.530 二叉搜寻树的最小相对差

给你一棵所有节点为非负值的二叉搜寻树，请你计算树中任意两节点的差的绝对值的最小值。

 

示例：

输出：

  1
   \
    3
   /
  2

输入：
1

解释：
最小相对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
 

提醒：

树中至多有 2 个节点。
本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 雷同

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划一：
/*
 * @lc app=leetcode.cn id=530 lang=javascript
 *
 * [530] 二叉搜寻树的最小相对差
 */

// @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 getMinimumDifference = function(root) {
    // 中序遍历
    const inorderTraversal = root => {const r = [];

        const recurse = root => {if(!root) return;
            recurse(root.left);
            r.push(root.val);
            recurse(root.right);
        }
            
        recurse(root);

        return r;
    };

    const arr = inorderTraversal(root);

    let min = Infinity;

    for(let p1=0, p2=1; p2 < arr.length; p1++, p2++) {if( min > arr[p2]-arr[p1] ) min = arr[p2]-arr[p1] 
    };

    return min;
};
计划二：
/*
 * @lc app=leetcode.cn id=530 lang=javascript
 *
 * [530] 二叉搜寻树的最小相对差
 */

// @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 getMinimumDifference = function(root) {
    let ans = Number.MAX_SAFE_INTEGER, pre = -1;
    const dfs = (root) => {if (root === null) {return;}
        dfs(root.left);
        if (pre == -1) {pre = root.val;} else {ans = Math.min(ans, root.val - pre);
            pre = root.val;
        }
        dfs(root.right);
    }
    dfs(root);
    return ans;
};

还是利用中序遍历进行扩大，有两种计划：1、中序遍历后升序数组进行最小差值输入；2、优化额定的数组空间，利用几个指针，在中序遍历中进行判断输入

2020.11.26

No.669 修剪二叉搜寻树

给你二叉搜寻树的根节点 root，同时给定最小边界 low 和最大边界 high。通过修剪二叉搜寻树，使得所有节点的值在 [low, high] 中。修剪树不应该扭转保留在树中的元素的绝对构造（即，如果没有被移除，原有的父代子代关系都该当保留）。能够证实，存在惟一的答案。

所以后果该当返回修剪好的二叉搜寻树的新的根节点。留神，根节点可能会依据给定的边界产生扭转。

 

示例 1：

输出：root = [1,0,2], low = 1, high = 2
输入：[1,null,2]
示例 2：

输出：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输入：[3,2,null,1]
示例 3：

输出：root = [1], low = 1, high = 2
输入：[1]
示例 4：

输出：root = [1,null,2], low = 1, high = 3
输入：[1,null,2]
示例 5：

输出：root = [1,null,2], low = 2, high = 4
输入：[2]
 

提醒：

树中节点数在范畴 [1, 104] 内
0 <= Node.val <= 104
树中每个节点的值都是惟一的
题目数据保障输出是一棵无效的二叉搜寻树
0 <= low <= high <= 104

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/trim-a-binary-search-tree
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划：
/*
 * @lc app=leetcode.cn id=669 lang=javascript
 *
 * [669] 修剪二叉搜寻树
 */

// @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
 * @param {number} low
 * @param {number} high
 * @return {TreeNode}
 */
var trimBST = function(root, low, high) {
    // 递归终止条件
    if(!root) return root;
    
    if(root.val >= low && root.val <= high) {
        // 满足要求，持续递归
        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
    } else {
        // 比最小值小，放弃左侧树，root 值为右侧值
        if(root.val < low) return trimBST(root.right, low, high);
        // 比最大值大，放弃右侧树，root 值为左侧值
        if(root.val > high) return trimBST(root.left, low, high);
    }

    return root;
};

失常递归思路，须要依据区间判断是否持续向下递归，当不满足条件时批改须要递归的 root 的值

总结：
  1. 二叉搜寻树问题常见的做法依然是递归去解决，这里最常利用的就是二叉搜寻树的中序遍历为升序数组进行相干扩大；
  2. 对于递归时产生的空间优化问题，能够通过指针等来优化栈空间等的应用，也可联合之前遍历问题中的工夫优化问题，提高效率
  3. 树的问题中有时也会波及数学相干的问题，可间接依据数学问题来解，如卡特兰数等

非凡二叉树问题

2020.11.27

No.101 对称二叉树

给定一个二叉树，查看它是否是镜像对称的。

 

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

   1
  / \
 2   2
/ \ / \
3  4 4  3
 

然而上面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

   1
  / \
 2   2
  \   \
  3    3
 

进阶：

你能够使用递归和迭代两种办法解决这个问题吗？

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/symmetric-tree
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划一：
/*
 * @lc app=leetcode.cn id=101 lang=javascript
 *
 * [101] 对称二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    // 中序遍历 + 层数
    const inorderLevelTraversal = function(root) {const r = [];
        const recurse = (node, n) => {if(!node) return;
            n++;
            recurse(node.left, n);
            r.push([node.val,n])
            recurse(node.right, n);
        };

        recurse(root, 0);
        return r;
    };
    const r = inorderLevelTraversal(root);
    console.log('r', r);
    // 判断中序遍历数组是否对称
    let p1 = 0,
        p2 = r.length - 1;
    while(p1 < p2) {if( r[p1][0] != r[p2][0] || r[p1][1] != r[p2][1] ) return false;
        p1++;
        p2--;
    };
    return true;
};
计划二：
/*
 * @lc app=leetcode.cn id=101 lang=javascript
 *
 * [101] 对称二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const isSymmetric = (root) => {const check = (left, right) => {if (left == null && right == null) { // 两个子树都为 null，是对称的
      return true;
    }
    if (left && right) {  // 两个子树都存在，则须要：root 值雷同，且他们的子树也满足镜像
      return left.val == right.val && check(left.left, right.right) && check(left.right, right.left);
    }
    return false;         // 一个子树存在一个不存在，必定不对称
  };

  if (root == null) {     // 如果传入的 root 就是 null，对称
    return true;
  }           
  return check(root.left, root.right); // 否则，判断它的左右子树是否满足对称
};
计划三：
/*
 * @lc app=leetcode.cn id=101 lang=javascript
 *
 * [101] 对称二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
const isSymmetric = (root) => {if (root == null) return true; 

  const queue = [];
  queue.push(root.left, root.right);  // 起初入列两个子树

  while (queue.length) {  // 队列清空就完结，没有节点可入列了
    const levelSize = queue.length; // 以后层的节点个数
    for (let i = 0; i < levelSize; i += 2) { // 以后层的节点成对入列
      const left = queue.shift();   
      const right = queue.shift();  // 出列一对节点
      if ((left && right == null) || (left == null && right)) { // 有一个存在有一个不存在
        return false;
      }
      if (left && right) { // 两个都存在
        if (left.val != right.val) { // 节点值不同，不对称
          return false;
        }
        queue.push(left.left, right.right); // 推入下一层的一对节点
        queue.push(left.right, right.left); // 推入下一层的一对节点
      }
    }
  }
  return true; // bfs 完结，始终没有返回 false，则返回真
};

有三种解法：1、参考中序遍历思路，判断中序遍历后的数组是否对称，这里须要退出层数来防止有一个节点为 null 无奈判断的情景；2、DFS 递归，间接递归判断；3、BFS 迭代，保护一个队列进行判断

2020.11.30

No.110 均衡二叉树

给定一个二叉树，判断它是否是高度均衡的二叉树。

本题中，一棵高度均衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

 

示例 1：

输出：root = [3,9,20,null,null,15,7]
输入：true
示例 2：

输出：root = [1,2,2,3,3,null,null,4,4]
输入：false
示例 3：

输出：root = []
输入：true
 

提醒：

树中的节点数在范畴 [0, 5000] 内
-104 <= Node.val <= 104

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balanced-binary-tree
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划一：
/*
 * @lc app=leetcode.cn id=110 lang=javascript
 *
 * [110] 均衡二叉树
 */

// @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 {boolean}
 */
var isBalanced = function(root) {
    // 获取树的高度
    const getTreeHeight = tree => {if(!tree) return true;
        return 1 + Math.max(getTreeHeight(tree.left),getTreeHeight(tree.right))
    };
    // 差值比拟后返回后果
    if(!root) return true;
    const lh = getTreeHeight(root.left),
          rh = getTreeHeight(root.right);
    // 如果后果有大于 1 的间接 false
    if(Math.abs(lh-rh) > 1 ) {return false;}
    return isBalanced(root.left) && isBalanced(root.right);
};
计划二：
/*
 * @lc app=leetcode.cn id=110 lang=javascript
 *
 * [110] 均衡二叉树
 */

// @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 {boolean}
 */
var isBalanced = function(root) {
    // 判断是否均衡
    const balanced = function (node) {if (!node) return 0
        const left = balanced(node.left)
        const right = balanced(node.right)
        if (left === -1 || right === -1 || Math.abs(left - right) > 1) {return -1}
        return Math.max(left, right) + 1
    }
    return balanced(root) !== -1;
};

有两种计划：1、自顶向下：获取左子树和右子树高度比拟，如果不合乎间接返回 false，否则向下递归；2、自底向上：相似后序遍历计划，先判断左子树，再判断右子树，再判断根节点，有不合乎就返回 false，否则向上递归

2020.12.01

No.226 翻转二叉树

翻转一棵二叉树。

示例：

输出：

    4
  /   \
 2     7
/ \   / \
1   3 6   9
输入：

    4
  /   \
 7     2
/ \   / \
9   6 3   1
备注:
这个问题是受到 Max Howell 的 原问题 启发的：

谷歌：咱们 90%的工程师应用您编写的软件(Homebrew)，然而您却无奈在面试时在白板上写出翻转二叉树这道题，这太蹩脚了。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/invert-binary-tree
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划一：
/*
 * @lc app=leetcode.cn id=226 lang=javascript
 *
 * [226] 翻转二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    let temp = null;
    const recurse = node => {if(!node) return;
        temp = node.left;
        node.left = node.right;
        node.right = temp;
        recurse(node.left);
        recurse(node.right);
    };
    recurse(root);
    return root;
};
计划二：
/*
 * @lc app=leetcode.cn id=226 lang=javascript
 *
 * [226] 翻转二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {if (!root) return root;
  const queue = [root];   // 保护一个队列，初始推入第一层的 root
  
  while (queue.length) {const cur = queue.shift(); // 入列的节点
    [cur.left, cur.right] = [cur.right, cur.left]; // 替换左右子树

    cur.left && queue.push(cur.left);
    cur.right && queue.push(cur.right);
  }
  
  return root;
};

面试考树最常考的题，两种计划：1、递归；2、迭代

2020.12.02

No.617 合并二叉树

给定两个二叉树，设想当你将它们中的一个笼罩到另一个上时，两个二叉树的一些节点便会重叠。

你须要将他们合并为一个新的二叉树。合并的规定是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将间接作为新二叉树的节点。

示例 1:

输出:

Tree 1                     Tree 2                  

         1                         2                            
        / \                       / \                            
       3   2                     1   3                        
      /                           \   \                      
     5                             4   7                  
输入:
合并后的树:
     3
    / \
   4   5
  / \   \
 5   4   7
留神: 合并必须从两个树的根节点开始。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-binary-trees
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划一：
/*
 * @lc app=leetcode.cn id=617 lang=javascript
 *
 * [617] 合并二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} t1
 * @param {TreeNode} t2
 * @return {TreeNode}
 */
var mergeTrees = function(t1, t2) {
    // 以 t1 为基准
    if(!t1) return t2;
    if(!t2) return t1;
    t1.val = t2.val + t1.val;
    t1.left = mergeTrees(t1.left, t2.left);
    t1.right = mergeTrees(t1.right, t2.right);
    return t1;
};
计划二：
/*
 * @lc app=leetcode.cn id=617 lang=javascript
 *
 * [617] 合并二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} t1
 * @param {TreeNode} t2
 * @return {TreeNode}
 */
var mergeTrees = function(t1, t2) {
    // 以 t1 为基准
    if(!t1) return t2;
    if(!t2) return t1;
    t1.val = t2.val + t1.val;
    // 结构栈空间迭代
    const stack = [[t1, t2]];
    while (stack.length) {const [p, q] = stack.shift();
        if (p.left && q.left) {
            p.left.val += q.left.val
            stack.push([p.left, q.left]);
        } else if (!p.left) p.left = q.left;
        else if (!q.left) q.left = p.left;

        if (p.right && q.right) {
            p.right.val += q.right.val;
            stack.push([p.right, q.right]);
        } else if (!p.right) p.right = q.right;
        else if (!q.right) q.right = p.right;
    }
    return t1;
};

同 226，树的基本操作，面试树常考，有两种计划：1、递归；2、迭代

2020.12.03

No.654 最大二叉树

给定一个不含反复元素的整数数组。一个以此数组构建的最大二叉树定义如下：

二叉树的根是数组中的最大元素。
左子树是通过数组中最大值右边局部结构出的最大二叉树。
右子树是通过数组中最大值左边局部结构出的最大二叉树。
通过给定的数组构建最大二叉树，并且输入这个树的根节点。

 

示例：

输出：[3,2,1,6,0,5]
输入：返回上面这棵树的根节点：

     6
   /   \
  3     5
   \    /
    2  0  
      \
       1
 

提醒：

给定的数组的大小在 [1, 1000] 之间。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-binary-tree
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划：
/*
 * @lc app=leetcode.cn id=654 lang=javascript
 *
 * [654] 最大二叉树
 */

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

典型的递归问题，以最大值作为宰割点

2020.12.04

No.655 输入二叉树

在一个 m*n 的二维字符串数组中输入二叉树，并恪守以下规定：

行数 m 该当等于给定二叉树的高度。
列数 n 该当总是奇数。
根节点的值（以字符串格局给出）该当放在可搁置的第一行正中间。根节点所在的行与列会将残余空间划分为两局部（左下局部和右下局部）。你应该将左子树输入在左下局部，右子树输入在右下局部。左下和右下局部该当有雷同的大小。即便一个子树为空而另一个非空，你不须要为空的子树输入任何货色，但仍须要为另一个子树留出足够的空间。然而，如果两个子树都为空则不须要为它们留出任何空间。
每个未应用的空间应蕴含一个空的字符串 ””。
应用雷同的规定输入子树。
示例 1:

输出:
    1
   /
  2
输入:
[[“”, “1”, “”],
[“2”, “”, “”]]
示例 2:

输出:
    1
   / \
  2   3
   \
    4
输入:
[[“”, “”, “”, “1”, “”, “”, “”],
[“”, “2”, “”, “”, “”, “3”, “”],
[“”, “”, “4”, “”, “”, “”, “”]]
示例 3:

输出:
     1
    / \
   2   5
  /
 3
/
4
输入:
[[“”,  “”,  “”, “”,  “”, “”, “”, “1”, “”,  “”,  “”,  “”,  “”, “”, “”]
[“”,  “”,  “”, “2”, “”, “”, “”, “”,  “”,  “”,  “”,  “5”, “”, “”, “”]
[“”,  “3”, “”, “”,  “”, “”, “”, “”,  “”,  “”,  “”,  “”,  “”, “”, “”]
[“4”, “”,  “”, “”,  “”, “”, “”, “”,  “”,  “”,  “”,  “”,  “”, “”, “”]]
留神: 二叉树的高度在范畴 [1, 10] 中。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/print-binary-tree
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划：
/*
 * @lc app=leetcode.cn id=655 lang=javascript
 *
 * [655] 输入二叉树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string[][]}
 */
var printTree = function(root) {
    // 获取树的高度
    const treeHeight = root => {if(!root) return 0;
        return treeHeight(root.left) > treeHeight(root.right) ? (treeHeight(root.left) + 1 ): (treeHeight(root.right) + 1);
    };
    // 填充输入值
    const printValue = (r, root, n, left, right) => {if(root) {let mid = Math.floor( ( left + right) / 2 );
        r[n][mid] = root.val + '';
        printValue(r, root.left, n+1, left, mid);
        printValue(r, root.right, n+1, mid+1, right)}
    };

    const m = treeHeight(root),
          n = Math.pow(2,m) - 1;
    console.log(m)
    const r = new Array(m);
    for(let i=0;i<m;i++) r[i]=new Array(n).fill('');
    printValue(r, root,0,0,n);
    return r;
};

二分法递归，学生成二维数组，再在对应地位填充值

2020.12.06

No.998 最大二叉树 -ii

最大树定义：一个树，其中每个节点的值都大于其子树中的任何其余值。

给出最大树的根节点 root。

就像之前的问题那样，给定的树是从表 A（root = Construct(A)）递归地应用下述 Construct(A) 例程结构的：

如果 A 为空，返回 null
否则，令 A[i] 作为 A 的最大元素。创立一个值为 A[i] 的根节点 root
root 的左子树将被构建为 Construct([A[0], A[1], …, A[i-1]])
root 的右子树将被构建为 Construct([A[i+1], A[i+2], …, A[A.length – 1]])
返回 root
请留神，咱们没有间接给定 A，只有一个根节点 root = Construct(A).

假如 B 是 A 的正本，并附加值 val。保障 B 中的值是不同的。

返回 Construct(B)。

 

示例 1：

输出：root = [4,1,3,null,null,2], val = 5
输入：[5,4,null,1,3,null,null,2]
解释：A = [1,4,2,3], B = [1,4,2,3,5]
示例 2：

输出：root = [5,2,4,null,1], val = 3
输入：[5,2,4,null,1,null,3]
解释：A = [2,1,5,4], B = [2,1,5,4,3]
示例 3：

输出：root = [5,2,3,null,1], val = 4
输入：[5,2,4,null,1,3]
解释：A = [2,1,5,3], B = [2,1,5,3,4]
 

提醒：

1 <= B.length <= 100

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-binary-tree-ii
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

计划：
/*
 * @lc app=leetcode.cn id=998 lang=javascript
 *
 * [998] 最大二叉树 II
 */

// @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
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoMaxTree = function(root, val) {
    // 中序遍历
    const 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;
    };

    // 数组的最大二叉树
    const constructMaximumBinaryTree = function(nums) {if(nums.length == 0) return null;
        const root = new TreeNode(Math.max(...nums));
        root.left = constructMaximumBinaryTree(nums.slice(0,nums.indexOf(Math.max(...nums))));
        root.right = constructMaximumBinaryTree(nums.slice(nums.indexOf(Math.max(...nums))+1));
        return root;
    };

    const A = inorderTraversal(root);
    A.push(val);
    return constructMaximumBinaryTree(A);
};

94 题和 655 题的综合，先求出中序遍历数组，在数组后增加 val 值，对新数组进行求最大树

总结：
  1. 非凡二叉树次要是树的不同状态的解决，常见的次要是递归和迭代，面试中经常要求都写进去；
  2. 依据不同要求获取树，算是树的根本考查，面试过程中如果考树，个别都会以非凡二叉树来测验

正文完
leetcode算法
发表至： leetcode算法
2021-08-09
 0
关于leetcode算法:前端常见算法题树篇
关于leetcode算法:leetcode35
关于leetcode算法:彩票调度算法
关于leetcode算法:leetcode-2413-最小偶倍数