57.二叉树的下一个结点
题目描述：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路分析：
给定节点可分为以下三种情况：
1.该节点有右子树节点，则下一个节点为右子树的最左端节点，在右子树不断向左遍历即可找到。
2.该节点为父节点的左子节点，则下一个节点为父节点。
3.该节点为父节点的右子节点，则需向上遍历找到某节点n为其父节点m的左子节点，即回到第二种情况，中序遍历的下一个节点为父节点m。
/*function TreeLinkNode(x){
this.val = x;
this.left = null;
this.right = null;
this.next = null;
}*/
function GetNext(pNode)
{
if (pNode === null) {return null;}
if (pNode.right) {
pNode = pNode.right;
while (pNode.left) {
pNode = pNode.left;
}
return pNode;
}
while (pNode.next) {
if (pNode.next.left === pNode) {
return pNode.next;
}
pNode = pNode.next;
}
return null;
}
58.对称的二叉树
题目描述：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路分析：类似镜像二叉树的那道题，采取递归的方式，不断比较左子树和右子树是否对称以及左子树的子树和右子树的子树是否对称。
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function isSymmetrical(pRoot)
{
if (pRoot === null) return true;
return Symmetrical(pRoot.left, pRoot.right);
function Symmetrical(left, right) {
//若左右子树均为空，则对称
if (left === null && right === null) {
return true;
}
//若左右子树其中一个为空，一个不为空，则不对称（二者皆空已被上一步排除掉）
if (left === null || right === null) {
return false;
}
//若左右子树值相等，则对称
//再递归左子树的左右子树和右子树的左右子树是否对称
if (left.val === right.val) {
return Symmetrical(left.left, right.right) &&
Symmetrical(left.right, right.left);
}
}
}
59.按之字形顺序打印二叉树
题目描述：请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
思路分析：本题和层序遍历二叉树类似，但是注意奇数行从左往右，偶数行从右往左。可以用一个奇数栈和一个偶数栈分别存储，但push的顺序不同，一个从右往左，一个从左往右。
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function Print(pRoot)
{
const stackOdd = [];
const stackEven = [];
const lists = [];
if (pRoot === null) return lists;
stackOdd.push(pRoot);
let i = 1;
while (stackOdd.length !== 0 || stackEven.length !== 0) {
const list = [];
//奇数层
if (i % 2 === 1) {
while (stackOdd.length !== 0) {
let temp = stackOdd.pop();
list.push(temp.val);
if (temp.left) {
stackEven.push(temp.left);
}
if (temp.right) {
stackEven.push(temp.right);
}
}
} else {
//偶数层
while (stackEven.length !== 0) {
let temp = stackEven.pop();
list.push(temp.val);
if (temp.right) {
stackOdd.push(temp.right);
}
if (temp.left) {
stackOdd.push(temp.left);
}
}
}
i++;
lists.push(list);
}
return lists;
}
60.把二叉树打印成多行
题目描述：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
思路分析：在层序遍历的基础上，设置两个变量nextLevel存储下一层要打印的节点数，toBePrinted存储本层待打印的节点。
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function Print(pRoot)
{
const queue = [];
const res = [];
if (pRoot === null) return res;
let nextLevel = 0;
let toBePrinted = 1;
let list = [];
queue.push(pRoot);
while (queue.length) {
let temp = queue.shift();
list.push(temp.val);
toBePrinted--;
if (temp.left) {
queue.push(temp.left);
nextLevel++;
}
if (temp.right) {
queue.push(temp.right);
nextLevel++;
}
if (toBePrinted === 0) {
res.push(list);
list = [];
toBePrinted = nextLevel;
nextLevel = 0;
}
}
return res;
}
61.序列化二叉树
题目描述：请实现两个函数，分别用来序列化和反序列化二叉树
二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#），以 ！ 表示一个结点值的结束（value!）。
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。
例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树。
思路分析：采用先序遍历的方式。
const arr = [];
function Serialize(pRoot) {
// write code here
if (pRoot === null) {
arr.push('a');
} else {
arr.push(pRoot.val);
Serialize(pRoot.left);
Serialize(pRoot.right);
}
}
function Deserialize() {
// write code here
let node = null;
if (arr.length < 1) {
return null;
}
const number = arr.shift();
if (typeof number === 'number') {
node = new TreeNode(number);
node.left = Deserialize();
node.right = Deserialize();
}
return node;
}
