二叉树的一些解题思路与模板

二叉树的一些解题思路与模板,第1张

二叉树的一些解题思路与模板 完全二叉树 概念

完全二叉树是可以没有右子树,不能没有左子树。

解题思路

判断是否是一颗完全二叉树:使用层序遍历方法,如果发现有右无左或者发现第一个左右节点不双全,则后面节点必须都为叶子节点,否则不是完全二叉树。

二叉搜索树(BST) 概念

二叉搜索树(BST):每个节点的左子树数据都小于该节点数据,右子树大于该节点数据

解题思路

判断是否是一颗二叉搜索树:中序遍历,该数组一定为升序数组。

满二叉树 概念

满二叉树:除叶子结点,所有结点都有左右子树。

解题思路

判断是否为满二叉树:先统计该树的最大深度L,再统计该树的节点数N,满足N = 2^L - 1则为满二叉树

平衡二叉树 概念

平衡二叉树:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

解题思路

以剑指offer的JZ79 判断是不是平衡二叉树为例。根据概念,先写出求解深度的一个函数,然后写判断条件:1、空树也是平衡二叉树,返回true。2、左右两个子树的高度差的绝对值不超过1。最后因为是要每个子树都是平衡二叉树而不是只从根节点,所以也要递归IsBalanced_Solution该方法。

function IsBalanced_Solution(pRoot)
{
    // write code here
    function depth(r){
        if(r === null){
            return 0
        }
        return Math.max(depth(r.left),depth(r.right)) + 1
    }
    if(pRoot === null){
        return true
    }
    return Math.abs(depth(pRoot.left) - depth(pRoot.right)) <= 1 && IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right)
}
module.exports = {
    IsBalanced_Solution : IsBalanced_Solution
};
对称二叉树 概念

对称二叉树:以根节点为对称轴,左右子树成轴对称的树。

解题思路

以剑指offer的JZ28 对称的二叉树为例。使用层序遍历的方法进行判断。先准备一个队列,将根节点入队两次(因为每次要两两进行比较,出队的时候要出队两次),每次都要出队两次,判断:1、是否都为空,是的话跳过该次循环。2、判断出队的两个是否出现有一个不存在(因为是对称二叉树)。3、判断两个值是否相同,不相同直接返回false。然后入队顺序为queue.push(a.left); queue.push(b.right); queue.push(a.right); queue.push(b.left);(因为出队后,需要两两比较它的值)

function isSymmetrical(pRoot)
{
    // write code here
    if(pRoot === null){
        return true
    }
    let queue = []
    
    queue.push(pRoot)
    queue.push(pRoot)
    while(queue.length !== 0){
        let a = queue.shift()
        let b = queue.shift()
        if(a === null && b === null){
            continue
        }
        if((!a && b) || (!b && a)){
            return false
        }
        if(a.val !== b.val){
            return false
        }
        queue.push(a.left)
        queue.push(b.right)
        queue.push(a.right)
        queue.push(b.left)
    }
    return true
}
module.exports = {
    isSymmetrical : isSymmetrical
};
二叉树遍历(递归模板)

// 先序遍历
let res = []
function print(tree){
	if(tree === null){
		return 
	}
	res.push(tree)
	print(tree.left)
	print(tree.right)
}

// 中序遍历
let res = []
function print(tree){
	if(tree === null){
		return 
	}
	print(tree.left)
	res.push(tree)
	print(tree.right)
}

// 后序遍历
let res = []
function print(tree){
	if(tree === null){
		return 
	}
	print(tree.left)
	print(tree.right)
	res.push(tree)
}
二叉树遍历(非递归模板) 先序遍历

算法步骤:
1、先将头放入栈中
2、从栈中d出一个节点
3、打印(处理)cur
4、先右再左(如果有)
5、直到栈中无元素结束

if(root !== null){
    let s1 = []
    let s2 = []
    s1.push(root)
    while(s1.length !== 0){
        let root = s1.pop()
        s2.push(root.val)
        if(root.right !== null){
            s1.push(root.right)
        }
        if(root.left !== null){
            s1.push(root.left)
        }
    }
    return s2;
}
return []
后序遍历

算法步骤:
1、先将头放入栈中
2、从栈中d出一个节点cur
3、cur放入收集栈
4、先左再右
5、直到栈中无元素结束,打印收集栈的出栈顺序,即为后序遍历

if(root !== null){
    let s1 = []
    let s2 = []
    s1.push(root)
    while(s1.length !== 0){
        root = s1.pop()
        s2.push(root.val)
        if(root.left !== null){
            s1.push(root.left)
        }
        if(root.right !== null){
            s1.push(root.right)
        }
    }
    return s2.reverse();
}
return []
中序遍历

解题思路:从根节点一直往左入栈,直到为空,就出栈并记录为root,然后再到该root的右子树,继续往左。

if(root !== null){
    let stack = []
    let s = []
    while(stack.length !== 0 || root !== null){
        if(root != null){
            stack.push(root)
            root = root.left
        } else{
            root = stack.pop()
            s.push(root.val)
            root = root.right
        }
    }
    return s
}
return []
层序遍历

解题思路:准备一个队列,先将根节点入队,每次循环出队一次,然后把出队的节点的左右节点都入队,最后出队的顺序就是层序遍历的顺序。

if(root === null){
    return 
} 
let queue = []
queue.push(head)
while(queue.length !== 0){
    let cur = queue.shift()
    console.log(cur)
    if(cur.left !== null){
        queue.push(cur.left)
    }
    if(cur.right !== null){
        queue.push(cur)
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5710430.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存