104. 二叉树的最大深度
首先是层序遍历
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
//思路1:显然层序遍历;
//思路2:似乎dfs是可行的,但?
var maxDepth = function(root) {
if(root===null){
return 0;
}
let depth = 0;
let queue = [];
let num = 1;
queue.push(root);
while(num>0){
for(let i = 0;i<num;i++ ){
let node = queue.shift()
if(node.left){
queue.push(node.left)
}
if(node.right){
queue.push(node.right)
}
}
depth++
num = queue.length
}
return depth
};
然后是递归dfs(前序); 参数为上一层深度,返回值为子数深度较大的一个;
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
//思路1:显然层序遍历;
//思路2:似乎dfs是可行的,但?
var maxDepth = function(root) {
return preOrder(root,0)
};
function preOrder(node,depth){
if(node == null){
return depth
}
return Math.max(preOrder(node.left,depth+1),preOrder(node.right,depth+1))
}
然后是dfs非递归, 感觉也就那么回事吧;不过效率居然比递归还慢点(虽然实现上确实几乎没差,没优化)
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
//思路1:显然层序遍历;
//思路2:似乎dfs是可行的,但?
var maxDepth = function(root) {
if(root == null){
return 0
}
let stack = []
stack.push([root,1])
let maxDepth = 1
while(stack.length>0){
let [node,depth] = stack.pop()
if(depth>maxDepth){
maxDepth = depth
}
if(node.right){
stack.push([node.right,depth+1])
}
if(node.left){
stack.push([node.left,depth+1])
}
}
return maxDepth
};
222.完全二叉树的节点个数
不能简单移植上面的递归算法,因为一定要算到叶子结点
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
//思路:递归,dfs,前序遍历,传入结点,深度,返回子树最小深度;结点为空终止;深度+1
//结果:不行, 因为要的是叶子结点的深度;空节点不算深度的方法不行了
var minDepth = function(root) {
return preOrder(root,0)
};
function preOrder(node,depth){
if(node==null){
return depth
}
if(node.left == null&&node.right==null){
return depth+1
}
else if(node.left == null&&node.right!=null){
return preOrder(node.right,depth+1)
}else if (node.left!=null&&node.right==null){
return preOrder(node.left,depth+1)
}else{
return Math.min(preOrder(node.left,depth+1),preOrder(node.right,depth+1))
}
}
非递归,层序
结果还是递归更快,不能理解
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
//思路:迭代,层序遍历
var minDepth = function(root) {
if(root == null){
return 0
}
let queue = []
queue.push(root)
let num =1
let depth = 1
while(num>0){
for(let i = 0; i< num;i++){
let node = queue.shift()
if(node.left){
queue.push(node.left)
}
if(node.right){
queue.push(node.right)
}
if(node.left==null&&node.right==null){
return depth
}
}
num = queue.length
depth++
}
};
顺便,看了卡哥的代码后,发现递归有更简便的写法,不需要传depth,只需要返回时候+1就行了(后序)
另外,所谓更规范的前序应该是,不返回(因为前序),而是在遍历到空后,赋值全局变量
222.完全二叉树的节点个数
首先是后序的暴力,居然效率还可以
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
//思路:首先是暴力,任意一种遍历都可以,前序和层序最为方便
//然后是求深度以及找到最后一个叶子结点,2^n-1+x
var countNodes = function(root) {
return postOrder(root)
};
var postOrder = function(node){
if(node == null){
return 0
}
return postOrder(node.left)+postOrder(node.right)+1
}
看了文章后,发现这种写法虽然简便,但不适合打基础,应该详细标注出中间结果比较好
利用完全二叉树性质的我想不出能提高效率的,脱裤子放屁那种除外
看了卡哥文章后发现能用左孩子遍历和右孩子遍历的长度判断是否是满二叉树;
然后判断局部是否是满二叉树,是则直接计算,否则递归算两边的数量之和
效率反而降低了...原因不明
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {number}
*/
//思路:首先是暴力,任意一种遍历都可以,前序和层序最为方便
//然后是求深度以及找到最后一个叶子结点,2^n-1+x
var countNodes = function(root) {
return postOrder(root)
};
var postOrder = function(node){
if(node == null){
return 0
}
let lNum = 0, rNum = 0
let p = node
while(p!=null){
p = p.left
lNum++
}
p = node
while(p!=null){
p = p.right
rNum++
}
if(lNum==rNum){
return Math.pow(2,lNum)-1
}
return postOrder(node.left)+postOrder(node.right)+1
}