二叉树的递归套路
可以解决面试中绝大多数（95%）的二叉树问题，尤其是树型dp问题
本质是利用递归遍历二叉树的便利性，就是一个结点会到达三次
补充一点，刷题中小技巧多如牛毛，大技巧就两个：二叉树的递归套路、暴力递归改动态规划的套路，这是总的指导思想。
所谓二叉树的递归套路就是在树上做动态规划，什么是动态规划呢？动态规划就是用时间换空间的方式。
二叉树的递归套路
1)假设以X节点为头，假设可以向X左树和X右树要任何信息
2)在上一步的假设下，讨论以X为头节点的树，得到答案的可能性(最重要)
3)列出所有可能性后，确定到底需要向左树和右树要什么样的信息
4)把左树信息和右树信息求全集，就是任何一棵子树都需要返回的信息S
5)递归函数都返回S，每一棵子树都这么要求
6)写代码，在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息
【题目】
给定一颗二叉树的头节点head，返回这颗二叉树是不是平衡二叉树
什么是平衡树：在一棵二叉树中，每一颗子树左树的高度与右树的高度差不超过1
所以判断一棵树是不是平衡二叉树的条件：
1）左树平衡
2）右树平衡
3）左树与右树高度差不超过1
package com.harrison.class08; public class Code01_IsBalanced { public static class Node { public int value; public Node left; public Node right; public Node(int data) { this.value = data; } } public static class Info{ public boolean isBalanced; public int height; public Info(boolean i,int h) { isBalanced=i; height=h; } } public static boolean isBalanced1(Node head) { return processs1(head).isBalanced; } public static Info processs1(Node head) { if(head==null) { return new Info(true, 0); } Info leftInfo=processs1(head.left); Info rightInfo=processs1(head.right); int height=Math.max(leftInfo.height, rightInfo.height)+1; boolean isBalanced=true; if(!leftInfo.isBalanced || !rightInfo.isBalanced || Math.abs(leftInfo.height-rightInfo.height)>1) { isBalanced=false; } return new Info(isBalanced, height); } public static boolean isBalanced2(Node head) { boolean[] ans=new boolean[1]; ans[0]=true; process2(head, ans); return ans[0]; } public static int process2(Node head,boolean[] ans) { if(!ans[0] || head==null) { return -1; } int leftHeight=process2(head.left,ans); int rightHeight=process2(head.right, ans); if(Math.abs(leftHeight-rightHeight)>1) { ans[0]=false; } return Math.max(leftHeight, rightHeight)+1; } public static Node generateRandomBST(int maxLevel,int maxValue) { return generate(1, maxLevel, maxValue); } public static Node generate(int level,int maxLevel,int maxValue) { if(level>maxLevel || Math.random()<0.5) { return null; } Node head=new Node((int)(Math.random()*maxValue)); head.left=generate(level+1, maxLevel, maxValue); head.right=generate(level+1, maxLevel, maxValue); return head; } public static void main(String[] args) { int testTimes=100000; int maxLevel=10; int maxValue=100; for(int i=0; i<testTimes; i++) { Node head=generateRandomBST(maxLevel, maxValue); if(isBalanced1(head)!=isBalanced2(head)) { System.out.println("oops"); } } System.out.println("finish"); } }
