1. 递归
递归问题可以总结成递归三部曲，即递归函数的构建，递归终止条件的确定和单次递归函数的确立这三个方面；完成了这三方面的工作后，相关问题递归算法的实现会容易许多。下面递归来实现用二叉树的前序遍历：
var preorderTraversal = function (root) {
const result = [];
const preTree = function (root) {
if (!root) {
return null;
}
result.push(root.val);
preTree(root.left);
preTree(root.right);
};
preTree(root);
return result;
};
|
在二叉树的递归函数返回值处理中，如果递归函数有返回值，如何区分要搜索一条边，还是搜索整个树呢？详细解释看这里。
搜索一条边的写法：
if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;
|
搜索整个树写法：
left = 递归函数(root->left);
right = 递归函数(root->right);
left与right的逻辑处理;
|
二叉树的遍历如果采用递归方法的话相对来说比较简单，逻辑比较清晰。下面着重介绍二叉树的迭代方法
2. 迭代
递归的实现就是每一次递归调用都会将函数的局部变量、参数和返回地址等压入调用的栈中，然后等递归返回的时候从栈中弹出各项参数。因此我们可以直接用栈来实现二叉树的遍历。这里总结的迭代方法，二叉树前中后序上比较通用易理解的方法。
前序 法1：先序节点的访问顺序是中左右，这个方法里是直接顺序记录的，按照中左右的顺序遍历出二叉树节点；
var preOrderTraversal = function(root) {
const stack=[],result=[];
let cur=root;
while(stack.length||cur){
if(cur){
result.push(cur.val);
stack.push(cur);
cur=cur.left;
}else{
cur=stack.pop();
cur=cur.right;
}
}
return result;
};
|
前序 法2：这个方法里前序前序中的左右在入栈的时候顺序应该调换一下，变成中右左，因为栈先入先出，记录的结果就为左右
var preOrderTraversal = function (root) {
const stack = [], result = [];
if (root) {
stack.push(root)
}
while (stack.length) {
const node = stack.pop();
result.push(node.val);
if (node.right) {
stack.push(node.right);
}
if (node.left) {
stack.push(node.left);
}
}
return result;
};
|
中序： 上述两个前序的方法，第一种稍加更改可以很方便的用来实现中序遍历，法1无需考虑进出栈顺序，中序读取顺序是左中右
var inOrderTraversal = function (root) {
const stack = [],
results = [];
while (stack.length || root) {
if (root) {
stack.push(root);
root = root.left;
} else {
root = stack.pop();
results.push(root.val);
root = root.right;
}
}
return results;
};
|
后序：后序遍历和前序的法2类似，后序遍历是左右中，前序的法2中出栈结果是中左右，为前序遍历结果，将法2的左右顺序调换，出栈结果为中右左，然后将结果数组逆序，得到后序遍历结果，代码如下：
var postorderTraversal = function (root) {
const stack = [], results = [];
if (root) {
stack.push(root);
}
while (stack.length) {
const node = stack.pop();
results.push(node.val);
if (node.left) {
stack.push(node.left)
}
if (node.right) {
stack.push(node.right)
}
}
return results.reverse();
};
|
总结：前序两种方法要深入理解，两种方法分别对应着中序和后序的迭代遍历实现，这是我目前了解到的比较简单的方法。
3. 层序遍历
二叉树的层序遍历主要是借助队列来实现，队列中每次保存的都是当前一层的信息，原理就不过多的赘述了，代码如下：
var levelOrder = function (root) {
if (!root) {
return []
}
const queue = [root], results = [];
while (queue.length) {
let level = [], size = queue.length;
while (size--) {
const node = queue.shift();
level.push(node.val);
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
results.push(level);
}
return results;
};
|
提示：求二叉树的深度等问题用层序很容易解决
4. 判断相同的二叉树/对称
判断二叉树对称/相同这里是借助队列来实现，（类似层序）队列中每次保存的都是当前一层的信息，判断相同的话将左右孩子入队顺序调换就可以了，也有在此基础上判断是否子数的，但是我觉得有些复杂，判断子树不如两个树的前序节点值前后加标识，空子树用另外替换，然后include判断的方法，代码和解释如下：
var isSymmetric = function(root) {
if(root===null){
return true
}
let queue = []
queue.push(root.left)
queue.push(root.right)
while(queue.length){
let leftNode = queue.shift()
let rightNode = queue.shift()
if(leftNode===null&&rightNode===null){
continue
}
if(leftNode===null||rightNode===null||leftNode.val!==rightNode.val){
return false
}
queue.push(leftNode.left)
queue.push(rightNode.right)
queue.push(leftNode.right)
queue.push(rightNode.left)
}
return true
};
|
