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

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

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

解题思路

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

二叉搜索树（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)
    }
}