本文共 2613 字，大约阅读时间需要 8 分钟。

此篇写的是二叉树的三种常用套路：

（1）二叉树的最大高度 （2）二叉树按层打印 （3）二叉树的所有路径 这三种套路是每个都可以解决一大类问题例如（3）可以解决力扣中的二叉树的所有路径，以及路径总和等等问题，虽然这种解法不是最优的，可却是一种套路，仅供大家参考～～～ 后序我会写出具体问题的更优化的解法。ps：以一种类型题入手，写出套路。

1. 平衡二叉树

出自：力扣110 题目描述： 给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

3   / \  9  20    /  \   15   7

返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

1      / \     2   2    / \   3   3  / \ 4   4

返回 false 。

解决套路： 注意： a. 左子树是平衡二叉树 b. 右子树是平衡二叉树 c. 左右子树高度不超过1

class Solution {    public boolean isBalanced(TreeNode root) {        //如果是颗空树		 if(root==null) {			 return true;		 }		 //否则，找左右高度，		 int left=getDepth(root.left);		 int right=getDepth(root.right);		return (Math.abs(left-right)<=1 && isBalanced(root.left) && isBalanced(root.right));	}	 //获取左右最大高度	private int getDepth(TreeNode root) {		if(root==null) {			return 0;		}		int left=getDepth(root.left);		int right=getDepth(root.right);		return Math.max(left, right)+1;	}}

这种解法同样适用于：104. 二叉树的最大深度等等关于二叉树深度的问题。

2. 二叉树层次遍历 出自力扣102 题目描述： 给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。 例如: 给定二叉树: [3,9,20,null,null,15,7],

3   / \  9  20    /  \   15   7

返回其层次遍历结果：

[ [3],[9,20],[15,7]] 解题思路：

class Solution {    public List
   
    
     > levelOrder(TreeNode root) {         List
     
      
       > list=new ArrayList<>();		 //健壮性判断			if(root==null){	            return list;	        }			Queue
       
         que=new LinkedList
        
         (); que.add(root); while(!que.isEmpty()) { int size=que.size(); List
         
           al=new ArrayList<>(); for(int i=0;i
         
        
       
      
     
    
   

这种解法可以解决:103. 二叉树的锯齿形层次遍历,只需要将list的奇数行反转即可（Collections.reverse(list.get(i));）等一列的关于按层输出的问题。

3. 二叉树的所有路径 出自力扣112 题目描述： 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

示例:

给定如下二叉树，以及目标和 sum = 22，

5         / \        4   8       /   / \      11  13  4     /  \      \    7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

解决方案：

class Solution {    public boolean hasPathSum(TreeNode root, int sum) {        if(root==null){            return false;        }        List
   
    
     > list=new ArrayList<>();		getAllDes(list,new ArrayList
     
      (),root);		for(int i=0;i
      
       > list, ArrayList
       
         al, TreeNode root) {		if(root!=null) {			al.add(root.val);		}		if(root.left==null && root.right==null) {			list.add(al);		}		if(root.left!=null) {			ArrayList
        
          al1=new ArrayList<>(al); getAllDes(list,al1,root.left); } if(root.right!=null) { ArrayList
         
           al1=new ArrayList<>(al); getAllDes(list,al1,root.right); } }}
         
        
       
      
     
    
   

这种解法可以解决257. 二叉树的所有路径等等关于路径的题。

最后声明：以上算法不一定是最优的，只是一种解题的固定套路适合解决一大类问题！！！