二叉树的前序遍历、中序遍历、后序、层序遍历的递归、迭代(含莫里斯)、序列化和反序列化实现代码

2022-05-11 19:30:50
二叉树的前序遍历、中序遍历、后序、层序遍历的递归、迭代(含莫里斯)以及序列化和反序列化实现方式,求解《97. 二叉树的序列化与反序列化》和《449. 序列化和反序列化二叉搜索树》

前序遍历

递归

const preorderTraversal = root => {
  const r = []
  const d = n => {
    if (n === null) return
    r.push(n.val)
    d(n.left)
    d(n.right)
  }
  d(root)
  return r
}
func preorderTraversal(root *TreeNode) []int {
  r := []int{}
  var d func(n *TreeNode)
  d = func(n *TreeNode)  {
    if n == nil {
      return
    }
    r = append(r, n.Val)
    d(n.Left)
    d(n.Right)
  }
  d(root)
  return r
}
class Solution {
  public $r = [];
  function preorderTraversal($root) {
    $this->d($root);
    return $this->$r ?? [];
  }
  function d($n) {
    if ($n === null) return;
    $this->$r []= $n->val;
    $this->d($n->left);
    $this->d($n->right);
  }
}
function preorderTraversal(root: TreeNode | null): number[] {
  const r: number[] = []
  const d = (n: TreeNode | null) => {
    if (n === null) return
    r.push(n.val)
    d(n.left)
    d(n.right)
  }
  d(root)
  return r
};

迭代

var preorderTraversal = function(root) {
  if (!root) return []
  const stack = [root], r = []
  while (stack.length) {
    const n = stack.pop()
    r.push(n.val)
    if (n.right) stack.push(n.right)
    if (n.left) stack.push(n.left)
  }
  return r
};
func preorderTraversal(root *TreeNode) []int {
  if root == nil {
    return []int{}
  }
  stack, r := []*TreeNode{}, []int{}
  stack = append(stack, root)
  for len(stack) > 0 {
    n := stack[len(stack) - 1]
    stack = stack[:len(stack) - 1]
    r = append(r, n.Val)
    if n.Right != nil {
      stack = append(stack, n.Right)
    }
    if n.Left != nil {
      stack = append(stack, n.Left)
    }
  }
  return r
}
class Solution {
  function preorderTraversal($root) {
    if ($root === null) return [];
    $r = [];
    $stack = [$root];
    while (count($stack) > 0) {
      $n = array_pop($stack);
      $r []= $n->val;
      if ($n->right) $stack []= $n->right;
      if ($n->left) $stack []= $n->left;
    }
    return $r;
  }
}
function preorderTraversal(root: TreeNode | null): number[] {
  if (root === null) return []
  const r: number[] = []
  const stack: TreeNode[] = [root]
  while (stack.length) {
    const n: TreeNode = stack.pop()
    r.push(n.val)
    if (n.right) stack.push(n.right)
    if (n.left) stack.push(n.left)
  }
  return r
};

中序遍历

递归

var inorderTraversal = function(root) {
  r = []
  const d = n => {
    if (n === null) return 
    d(n.left)
    r.push(n.val)
    d(n.right)
  }
  d(root)
  return r
};
func inorderTraversal(root *TreeNode) []int {
  r := []int{}
  var d func(n *TreeNode)
  d = func(n *TreeNode) {
    if n == nil {
      return
    }
    d(n.Left)
    r = append(r, n.Val)
    d(n.Right)
  }
  d(root)
  return r
}
class Solution {
  private $r = [];
  function inorderTraversal($root) {
    $this->d($root);
    return $this->$r ?? [];
  }
  function d($n) {
    if ($n === null) return;
    $this->d($n->left);
    $this->$r []= $n->val;
    $this->d($n->right);
  }
}
function inorderTraversal(root: TreeNode | null): number[] {
  const r: number[] = []
  const d = (n: TreeNode | null) => {
    if (n === null) return 
    d(n.left)
    r.push(n.val)
    d(n.right)
  }
  d(root)
  return r
};

迭代 · 单栈

const inorderTraversal = root => {
  const stack = [], r = []
  let p = root
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    r.push(n.val)
    p = n.right
  }
  return r
}
func inorderTraversal(root *TreeNode) []int {
  if root == nil {
    return []int{}
  }
  stack, p, r := []*TreeNode{}, root, []int{}
  for len(stack) > 0 || p != nil {
    for p != nil {
      stack = append(stack, p)
      p = p.Left
    }
    n := stack[len(stack) - 1]
    r = append(r, n.Val)
    stack = stack[:len(stack) - 1]
    p = n.Right
  }
  return r
}
class Solution {
  function inorderTraversal($root) {
    if ($root === null) return [];
    $stack = $r = [];
    $p = $root;
    while (count($stack) > 0 || $p) {
      while ($p) {
        $stack [] = $p;
        $p = $p->left;
      }
      $n = array_pop($stack);
      $r []= $n->val;
      $p = $n->right;
    }
    return $r;
  }
}
function inorderTraversal(root: TreeNode | null): number[] {
  const stack: TreeNode[] = [], r: number[] = []
  let p = root
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    r.push(n.val)
    p = n.right
  }
  return r
};

迭代 · 莫里斯 · Morris

var inorderTraversal = function(root) {
  const r = []
  while (root) {
    if (root.left) {
      let p = root.left
      while (p.right && p.right !== root) p = p.right
      if (p.right === null) {
        p.right = root
        root = root.left
      } else {
        r.push(root.val)
        p.right = null
        root = root.right
      }
    } else {
      r.push(root.val)
      root = root.right
    }
  }
  return r
};
func inorderTraversal(root *TreeNode) []int {
  r := []int{}
  for root != nil {
    if root.Left != nil {
      p := root.Left
      for p.Right != nil && p.Right != root {
        p = p.Right
      }
      if p.Right == nil {
        p.Right = root
        root = root.Left
      } else {
        r = append(r, root.Val)
        p.Right = nil
        root = root.Right
      }
    } else {
      r = append(r, root.Val)
      root = root.Right
    }
  }
  return r
}
class Solution {
  function inorderTraversal($root) {
    $r = [];
    while ($root) {
      if ($root->left) {
        $p = $root->left;
        while ($p->right && $p->right != $root) $p = $p->right;
        if ($p->right === null) {
          $p->right = $root;
          $root = $root->left;
        } else {
          $r []= $root->val;
          $p->right = null;
          $root = $root->right;
        }
      } else {
        $r []= $root->val;
        $root = $root->right;
      }
    }
    return $r;
  }
}
function inorderTraversal(root: TreeNode | null): number[] {
  const r: number[] = []
  while (root) {
    if (root.left) {
      let p = root.left
      while (p.right && p.right !== root) p = p.right
      if (p.right === null) {
        p.right = root
        root = root.left
      } else {
        r.push(root.val)
        p.right = null
        root = root.right
      }
    } else {
      r.push(root.val)
      root = root.right
    }
  }
  return r
};

后序遍历

递归

var postorderTraversal = function(root) {
  const r = []
  const d = n => {
    if (n === null) return
    d(n.left)
    d(n.right)
    r.push(n.val)
  }
  d(root)
  return r
};
func postorderTraversal(root *TreeNode) []int {
  r := []int{}
  var d func(n *TreeNode)
  d = func(n *TreeNode) {
    if n == nil {
      return
    }
    d(n.Left)
    d(n.Right)
    r = append(r, n.Val)
  }
  d(root)
  return r 
}
class Solution {
  private $r = [];
  function postorderTraversal($root) {
    $this->d($root);
    return $this->$r ?? [];
  }
  function d($n) {
    if ($n == null) return;
    $this->d($n->left);
    $this->d($n->right);
    $this->$r []= $n->val;
  }
}
function postorderTraversal(root: TreeNode | null): number[] {
  const r: number[] = []
  const d = (n: TreeNode | null) => {
    if (n === null) return
    d(n.left)
    d(n.right)
    r.push(n.val)
  }
  d(root)
  return r
};

迭代 · 单栈

var postorderTraversal = function(root) {
  const stack = [], r = []
  let p = root, prev = null
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    if (n.right === null || n.right === prev) {
      r.push(n.val)
      prev = n
    } else {
      stack.push(n)
      p = n.right
    }
  }
  return r
};
func postorderTraversal(root *TreeNode) []int {
  stack, r, p := []*TreeNode{}, []int{}, root
  var prev *TreeNode
  for len(stack) > 0 || p != nil {
    for p != nil {
      stack = append(stack, p)
      p = p.Left
    }
    n := stack[len(stack) - 1]
    stack = stack[:len(stack) - 1]
    if n.Right == nil || n.Right == prev {
      r = append(r, n.Val)
      prev = n
    } else {
      stack = append(stack, n)
      p = n.Right
    }
  }
  return r
}
class Solution {
  function postorderTraversal($root) {
    $stack = $r = [];
    $p = $root;
    $prev = null;
    while (count($stack) > 0 || $p) {
      while ($p) {
        $stack []= $p;
        $p = $p->left;
      }
      $n = array_pop($stack);
      if ($n->right === null || $n->right === $prev) {
        $r []= $n->val;
        $prev = $n;
      } else {
        $stack []= $n;
        $p = $n->right;
      }
    }
    return $r;
  }
}
function postorderTraversal(root: TreeNode | null): number[] {
  const stack: TreeNode[] = [], r: number[] = []
  let p = root, prev = null
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    if (n.right === null || n.right === prev) {
      r.push(n.val)
      prev = n
    } else {
      stack.push(n)
      p = n.right
    }
  }
  return r
};

迭代 · 双栈

var postorderTraversal = function(root) {
  if (root === null) return []
  const stack = [root], outStack = [], r = []
  while (stack.length) {
    const n = stack.pop()
    outStack.push(n)
    if (n.left) stack.push(n.left)
    if (n.right) stack.push(n.right)
  }
  while (outStack.length) r.push(outStack.pop().val)
  return r
};
func postorderTraversal(root *TreeNode) []int {
  if root == nil {
    return []int{}
  }
  stack, outStack, r := []*TreeNode{}, []*TreeNode{}, []int{}
  stack = append(stack, root)
  for len(stack) > 0 {
    n := stack[len(stack) - 1]
    stack = stack[:len(stack) - 1]
    outStack = append(outStack, n)
    if n.Left != nil {
      stack = append(stack, n.Left)
    }
    if n.Right != nil {
      stack = append(stack, n.Right)
    }
  }
  for len(outStack) > 0 {
    r = append(r, outStack[len(outStack) - 1].Val)
    outStack = outStack[:len(outStack) - 1]
  }
  return r
}
class Solution {
  function postorderTraversal($root) {
    if ($root === null) return [];
    $stack = [$root];
    $outStack = $r = [];
    while (count($stack) > 0) {
      $n = array_pop($stack);
      $outStack []= $n;
      if ($n->left) $stack []= $n->left;
      if ($n->right) $stack []= $n->right;
    }
    while (count($outStack) > 0) $r []= array_pop($outStack)->val;
    return $r;
  }
}
function postorderTraversal(root: TreeNode | null): number[] {
  if (root === null) return []
  const stack: TreeNode[] = [root], outStack: TreeNode[] = [], r: number[] = []
  while (stack.length) {
    const n = stack.pop()
    outStack.push(n)
    if (n.left) stack.push(n.left)
    if (n.right) stack.push(n.right)
  }
  while (outStack.length) r.push(outStack.pop().val)
  return r
};

层序遍历


var levelOrder = function(root) {
  if (root === null) return []
  const q = [root], r = []
  while (q.length) {
    let l = q.length
    r.push([])
    while (l--) {
      const n = q.shift()
      r[r.length - 1].push(n.val)
      if (n.left) q.push(n.left)
      if (n.right) q.push(n.right)
    }
  }
  return r
};
func levelOrder(root *TreeNode) [][]int {
  if root == nil {
    return [][]int{}
  }
  q, r := []*TreeNode{}, [][]int{}
  q = append(q, root)
  for len(q) > 0 {
    r = append(r, []int{})
    for l := len(q); l > 0; l-- {
      n := q[0]
      q = q[1:]
      r[len(r) - 1] = append(r[len(r) - 1], n.Val)
      if n.Left != nil {
        q = append(q, n.Left)
      }
      if n.Right != nil {
        q = append(q, n.Right)
      }
    }
  }
  return r
}
class Solution {
  function levelOrder($root) {
    if ($root === null) return [];
    $q = [$root];
    $r = [];
    while (count($q) > 0) {
      $l = count($q);
      $r []= [];
      while ($l--) {
        $n = array_shift($q);
        $r[count($r) - 1] []= $n->val;
        if ($n->left) $q []= $n->left;
        if ($n->right) $q []= $n->right;
      }
    }
    return $r;
  }
}
function levelOrder(root: TreeNode | null): number[][] {
  if (root === null) return []
  const q: TreeNode[] = [root], r: number[][] = []
  while (q.length) {
    let l = q.length
    r.push([])
    while (l--) {
      const n = q.shift()
      r[r.length - 1].push(n.val)
      if (n.left) q.push(n.left)
      if (n.right) q.push(n.right)
    }
  }
  return r
};

例题

297. 二叉树的序列化与反序列化

序列化是将一个数据结构或者对象转换为连续的比特位的操作,进而可以将转换后的数据存储在一个文件或者内存中,同时也可以通过网络传输到另一个计算机环境,采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑,你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致,详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式,你也可以采用其他的方法解决这个问题。

答案

前序遍历

var serialize = function(root) {
  if (root === null) return 'null'
  const q = [root], ar = []
  while (q.length) {
    const n = q.pop()
    if (n === null) {
      ar.push('null')
      continue
    }
    ar.push(n.val)
    q.push(n.right)
    q.push(n.left)
  }
  return ar.join(',')
};
var deserialize = function(data) {
  const ar = data.split(',')
  let index = -1
  const d = () => {
    if (ar[++index] === 'null') return null
    const n = new TreeNode(ar[index])
    n.left = d()
    n.right = d()
    return n
  } 
  return d()
};

type Codec struct {}

func Constructor() (_ Codec) {
  return
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
  ar := []string{}
  var d func(n *TreeNode)
  d = func(n *TreeNode) {
    if n == nil {
      ar = append(ar, "nil")
      return
    }
    ar = append(ar, strconv.Itoa(n.Val))
    d(n.Left)
    d(n.Right)
  }
  d(root)
  return strings.Join(ar, ",")
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode { 
  ar, index := strings.Split(data, ","), -1
  var d func() *TreeNode
  d = func() *TreeNode {
    index++
    if ar[index] == "nil" {
      return nil
    }
    num, _ := strconv.Atoi(ar[index])
    return &TreeNode{
      num,
      d(),
      d(),
    }
  }
  return d()
}
class Codec {
  function __construct() {}

  function serialize($root) {
    if ($root === null) return 'null';
    $stack = [$root];
    $ar = [];
    while(count($stack) > 0) {
      $n = array_pop($stack);
      if ($n === null) {
        $ar []= 'null';
        continue;
      }
      $ar []= $n->val;
      $stack []= $n->right;
      $stack []= $n->left;
    }
    return implode(',', $ar);
  }

  function deserialize($data) {
    $ar = explode(',', $data);
    $index = -1;
    $d = function () use(&$d, &$ar, &$index) {
      $index++;
      if ($ar[$index] === 'null') return null;
      $n = new TreeNode(intval($ar[$index]));
      $n->left = $d();
      $n->right = $d();
      return $n;
    };
    return $d();
  }
}
function serialize(root: TreeNode | null): string {
  const ar: string[] = []
  const d = n => {
    if (n === null) {
      ar.push('null')
      return
    }
    ar.push('' + n.val)
    d(n.left)
    d(n.right)
  }
  d(root)
  return ar.join(',')
};
function deserialize(data: string): TreeNode | null {
  const ar: string[] = data.split(',')
  let index = -1
  const d = () => {
    if (ar[++index] === 'null') return null
    return new TreeNode(
      +ar[index],
      d(),
      d()
    )
  }
  return d()
};

449. 序列化和反序列化二叉搜索树

序列化是将数据结构或对象转换为一系列位的过程,以便它可以存储在文件或内存缓冲区中,或通过网络连接链路传输,以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串,并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。

答案

前序遍历

var serialize = function(root) {
  if (root === null) return ''
  const stack = [root], ar = []
  while (stack.length) {
    const n = stack.pop()
    ar.push(n.val)
    if (n.right) stack.push(n.right)
    if (n.left) stack.push(n.left)
  }
  return ar.join(',')
};
var deserialize = function(data) {
  const ar = data.length ? data.split(',') : []
  let index = 0
  const d = (low, high) => {
    if (index >= ar.length || ar[index] < low || ar[index] > high) return null
    const n = new TreeNode(+ar[index++])
    n.left = d(low, n.val)
    n.right = d(n.val, high)
    return n
  }
  return d(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER)
};
type Codec struct {}

func Constructor() (_ Codec) {
  return
}

func (this *Codec) serialize(root *TreeNode) string {
  if root == nil {
    return ""
  }
  ar := []string{}
  stack := []*TreeNode{}
  stack = append(stack, root)
  for len(stack) > 0 {
    n := stack[len(stack) - 1]
    ar = append(ar, strconv.Itoa(n.Val))
    stack = stack[:len(stack) - 1]
    if n.Right != nil {
      stack = append(stack, n.Right)
    }
    if n.Left != nil {
      stack = append(stack, n.Left)
    }
  }
  return strings.Join(ar, ",")
}

func (this *Codec) deserialize(data string) *TreeNode {
  var ar []string
  if data != "" {
    ar = strings.Split(data, ",")
  }
  index, n := 0, len(ar)
  var d func(low int, high int) *TreeNode 
  d = func(low int, high int) *TreeNode {
    if index >= n {
      return nil
    }
    num, _ := strconv.Atoi(ar[index])
    if num < low || num > high {
      return nil
    }
    index++
    return &TreeNode{num, d(low, num), d(num, high)}
  }
  return d(math.MinInt32, math.MaxInt32)
}
class Codec {
  private $index = 0;
  function __construct() {}
  function serialize($root) {
    if ($root === null) return '';
    $stack = [$root];
    $ar = [];
    while (count($stack) > 0) {
      $n = array_pop($stack);
      $ar []= $n->val;
      if ($n->right) $stack []= $n->right;
      if ($n->left) $stack []= $n->left;
    }
    return implode(',', $ar);
  }
  function deserialize($data) {
    $ar = $data !== '' ? explode(',', $data) : [];
    return $this->d($ar, PHP_INT_MIN, PHP_INT_MAX);
  }
  function d(&$ar, $low, $high) {
    if ($this->index >= count($ar) || $ar[$this->index] < $low || $ar[$this->index] > $high) return null;
    $n = new TreeNode(intval($ar[$this->index++]));
    $n->left = $this->d($ar, $low, $n->val);
    $n->right = $this->d($ar, $n->val, $high);
    return $n;
  }
}
function serialize(root: TreeNode | null): string {
  const ar: number[] = []
  const d = (n: TreeNode) => {
    if (n === null) return
    ar.push(n.val)
    d(n.left)
    d(n.right)
  }
  d(root)
  return ar.join(',')
};
function deserialize(data: string): TreeNode | null {
  const ar = data ? data.split(',') : []
  let index = 0
  const d = (low, high) => {
    if (index >= ar.length || ar[index] < low || ar[index] > high) return null
    const num = +ar[index++]
    return new TreeNode(
      num,
      d(low, num),
      d(num, high)
    )
  }
  return d(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER)
};

后序遍历

var serialize = function(root) {
  const stack = [], ar = []
  let p = root, prev = null
  while (stack.length || p) {
    while (p) {
      stack.push(p)
      p = p.left
    }
    const n = stack.pop()
    if (n.right === null || n.right === prev) {
      ar.push(n.val)
      prev = n
    } else {
      stack.push(n)
      p = n.right
    }
  } 
  return ar.join(',')
};
var deserialize = function(data) {
  const ar = data.length ? data.split(',') : []
  let index = ar.length - 1
  const d = (low, high) => {
    if (index < 0 || ar[index] < low || ar[index] > high) return null
    const n = new TreeNode(+ar[index--])
    n.right = d(n.val, high)
    n.left = d(low, n.val)
    return n
  }
  return d(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER)
};
type Codec struct {}

func Constructor() (_ Codec) {
  return
}

func (this *Codec) serialize(root *TreeNode) string {
  ar := []string{}
  var d func(n *TreeNode) 
  d = func(n *TreeNode) {
    if n == nil {
      return
    }
    d(n.Left)
    d(n.Right)
    s := strconv.Itoa(n.Val)
    ar = append(ar, s)
  }
  d(root)
  return strings.Join(ar, ",")
}

func (this *Codec) deserialize(data string) *TreeNode {
  var ar []string
  if data != ""  { 
    ar = strings.Split(data, ",")
  }
  index := len(ar) - 1
  var d func(low int, high int) *TreeNode
  d = func(low int, high int) *TreeNode {
    if index < 0 {
      return nil
    }
    num, _ := strconv.Atoi(ar[index])
    if num < low || num > high {
      return nil
    }
    index--
    return &TreeNode{Val: num, Right: d(num, high), Left: d(low, num)}
  }
  return d(math.MinInt32, math.MaxInt32)
}
class Codec {
  private $index = 0;
  function __construct() {}

  function serialize($root) {
    $stack = $ar = [];
    $p = $root;
    $prev = null;
    while (count($stack) > 0 || $p !== null) {
      while ($p !== null) {
        $stack []= $p;
        $p = $p->left;
      }
      $n = array_pop($stack);
      if ($n->right === null || $n->right === $prev) {
        $ar []= $n->val;
        $prev = $n;
      } else {
        $stack []= $n;
        $p = $n->right;
      }
    }
    return implode(',', $ar);
  }

  function deserialize($data) {
    $ar = $data !== '' ? explode(',', $data) : [];
    $this->index = count($ar) - 1;
    return $this->d($ar, PHP_INT_MIN, PHP_INT_MAX);
  }

  function d(&$ar, $low, $high) {
    if ($this->index < 0 || $ar[$this->index] < $low || $ar[$this->index] > $high) return null;
    $n = new TreeNode(+$ar[$this->index--]);
    $n->right = $this->d($ar, $n->val, $high);
    $n->left = $this->d($ar, $low, $n->val);
    return $n;
  }
}
function serialize(root: TreeNode | null): string {
  if (root === null) return ''
  const stack = [root], outStack = [], ar = []
  while (stack.length) {
    const n = stack.pop()
    outStack.push(n)
    if (n.left) stack.push(n.left)
    if (n.right) stack.push(n.right)
  }
  while (outStack.length) ar.push(outStack.pop().val)
  return ar.join(',')
};
function deserialize(data: string): TreeNode | null {
  const ar = data ? data.split(',') : []
  let index = ar.length - 1
  const d = (low, high) => {
    if (index < 0 || ar[index] < low || ar[index] > high) return null
    const n = new TreeNode(+ar[index--])
    n.right = d(n.val, high)
    n.left = d(low, n.val)
    return n
  }
  return d(Number.MIN_SAFE_INTEGER, Number.MAX_SAFE_INTEGER)
};

代码
递归、迭代:求解《953. 验证外星语词典》
递归、迭代两种方式,求解《953. 验证外星语词典》
代码
平衡二叉树性质:求解《面试题 04.06. 后继者》
用平衡二叉树性质,求解《面试题 04.06. 后继者》
代码
哈希表、队列、约瑟夫环的迭代和递归,动态规划求解《1823. 找出游戏的获胜者》和《剑指 Offer 62. 圆圈中最后剩下的数字》
哈希表、队列、递归、迭代,用约瑟夫环的递推公式,求解《1823. 找出游戏的获胜者》和《剑指 Offer 62. 圆圈中最后剩下的数字》