二叉树的前序遍历、中序遍历、后序、层序遍历的递归、迭代（含莫里斯）以及序列化和反序列化实现方式，求解《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
};class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> r = new ArrayList<Integer>();
Deque<TreeNode> stack = new ArrayDeque<TreeNode>();
TreeNode p = root;
TreeNode prev = null;
while (p != null || stack.isEmpty() != true) {
while (p != null) {
stack.push(p);
p = p.left;
}
TreeNode n = stack.pop();
if (n.right == null || n.right == prev) {
r.add(n.val);
prev = n;
} else {
stack.push(n);
p = n.right;
}
}
return r;
}
}class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
stack, p, prev, r = [], root, None, []
while p or len(stack):
while p:
stack.append(p)
p = p.left
n = stack.pop()
if n.right == None or n.right == prev:
r.append(n.val)
prev = n
else:
stack.append(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)
};
