本文主要包括树相关的算法，二叉树结点基本结构如下
function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
}
本文还会继续更新。
二叉树的深度
function depth(pRoot){
if(!pRoot){
return 0;
}
var depth = 0;
var currDepth = 0;
dfs(pRoot);
return depth;
function dfs(node){
if(!node){
depth = depth > currDepth ? depth : currDepth;
return;
}
currDepth++;
dfs(node.left);
dfs(node.right);
currDepth--;
}
}
二叉树的前序遍历
function preOrder(root){
if(!root)
return [];
var result = [];
_preOrder(root);
return result;
function _preOrder(node){
result.push(node.val);
node.left && _preOrder(node.left);
node.right && _preOrder(node.right);
}
}
二叉树的中序遍历
function inOrder(root){
if(!root)
return [];
var result = [];
_inOrder(root);
return result;
function _inOrder(node){
node.left && _inOrder(node.left);
result.push(node.val);
node.right && _inOrder(node.right);
}
}
二叉树的后序遍历
function postOrder(root){
if(!root)
return [];
var result = [];
_postOrder(root);
return result;
function _postOrder(node){
node.left && _postOrder(node.left);
node.right && _postOrder(node.right);
result.push(node.val);
}
}
二叉树的层序遍历
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function printFromTopToBottom(root){
if (!root) {
return [];
}
var queue = [];
queue.push(root);
var result = [];
while (queue.length) {
var temp = queue.shift();
result.push(temp.val);
if (temp.left) {
queue.push(temp.left);
}
if (temp.right) {
queue.push(temp.right);
}
}
return result;
}
根据层序遍历建立二叉树
//层序的空节点使用 null
function Tree(arr, node, num){ //也可以通过 new 调用
if(!arr || arr.length === 0){
return new TreeNode(null);
}
num = num || 1;
node = node || new TreeNode(arr[num - 1]);
var curr = node;
if(num * 2 - 1 < arr.length && arr[num * 2 - 1] != null){
curr.left = new TreeNode(arr[num * 2 - 1]);
Tree(arr, curr.left, num * 2);
}
if(num * 2 < arr.length && arr[num * 2] != null){
curr.right = new TreeNode(arr[num * 2]);
Tree(arr, curr.right, num * 2 + 1);
}
return node;
}
根据中序遍历和前序遍历重建二叉树
function reBuildTree_pi(pre, vin){
if(pre.length == 0 || vin.length == 0 || pre.length !== vin.length){
return null;
};
var index = vin.indexOf(pre[0]);
var left = vin.slice(0,index);
var right = vin.slice(index+1);
var node = new TreeNode(vin[index]);
node.left = reBuildTree_pi(pre.slice(1,index+1),left);
node.right = reBuildTree_pi(pre.slice(index+1),right);
return node;
}
根据中序遍历和后序遍历重建二叉树
function reBuildTree_ip(vin, post){
if(post.length == 0 || vin.length == 0 || vin.length !== post.length){
return null;
};
var index = vin.indexOf(post.pop());
var left = vin.slice(0,index);
var right = vin.slice(index+1);
var node = new TreeNode(vin[index]);
node.left = reBuildTree_ip(left, post.slice(0,index));
node.right = reBuildTree_ip(right, post.slice(index));
return node;
}
求二叉树的最远节点距离
function maxDistance(root){ //root 二叉树根节点；
if(root === null) return 0;
var max = 0;
_maxDistance(root, max);
return max; //函数返回最大值
function _maxDistance(curr){ //curr: 当前节点；max: 最大值；
if(curr === null) return 0;
var leftDepth = curr.left ? _maxDistance(curr.left) : 0;
var rightDepth = curr.right ? _maxDistance(curr.right) : 0;
if(leftDepth + rightDepth > max) max = leftDepth + rightDepth;
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
}
二叉树的镜像
function mirror(root){
if(!root){
return null;
}
var temp = root.left;
root.left = root.right;
root.right = temp;
if(root.left){
Mirror(root.left);
}
if(root.right){
Mirror(root.right);
}
}
二叉搜索树转双向链表
将左子树构成双向链表，返回的是左子树的尾结点，将其连接到root的左边；
将右子树构成双向链表，将其追加到root结点之后，并返回尾结点；
向左遍历返回的链表至头结点处，即为所求双向链表的首结点。
function convert(pRootOfTree){
if(!pRootOfTree) {
return null;
}
var lastNode = null;
lastNode = ConvertNode(pRootOfTree);
var head = lastNode;
while(head && head.left) {
head = head.left;
}
return head;
function ConvertNode(node){
if(!node){
return;
}
if(node.left) {
lastNode = ConvertNode(node.left);
}
node.left = lastNode;
if(lastNode){
lastNode.right = node;
}
lastNode = node;
if(node.right){
lastNode = ConvertNode(node.right);
}
return lastNode;
}
}
判断是否平衡二叉树
function isBalancedTree(pRoot){
if(!pRoot){
return true;
}
var left = TreeDepth(pRoot.left);
var right = TreeDepth(pRoot.right);
var diff = left - right;
if(diff > 1 || diff < -1)
return false;
return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
function TreeDepth(pRoot){
if(!pRoot){
return 0;
}
var depth = 0;
var currDepth = 0;
dfs(pRoot);
return depth;
function dfs(node){
if(!node){
depth = depth > currDepth ? depth : currDepth;
return;
}
currDepth++;
dfs(node.left);
dfs(node.right);
currDepth--;
}
}
}
判断是否对称二叉树
function isSymmetrical(pRoot){
if(!pRoot){
return true;
}
return symmetrical(pRoot, pRoot);
function symmetrical(node1,node2){
if(!node1 && !node2)
return true;
if(!node1 || !node2)
return false;
if(node1.val != node2.val)
return false;
return symmetrical(node1.left, node2.right) && symmetrical(node1.right, node2.left);
}
}
判断是否完全二叉树
function isPrefectTree(root){
if(!root)
return true;
var que = [];
que.push(root);
var curr;
while(curr = que.shift()){
que.push(curr.left);
que.push(curr.right);
}
while (que.length > 0){
if (que.pop())
return false;
}
return true;
}
判断是否满二叉树
function isFullTree(root){
if(!root)
return true;
var que = [];
que.push(root);
var curr;
var nodeNum = 0;
while(curr = que.shift()){
que.push(curr.left);
que.push(curr.right);
nodeNum++;
}
while (que.length > 0){
if (que.pop())
return false;
}
return (nodeNum & (nodeNum + 1)) === 0;
}
