[剑指offer]面试题第[55-2]题[Leetcode][第110题][JAVA][平衡二叉树][DFS][剪枝]

【问题描述】[中等]

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过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 。 限制： 1 <= 树的结点个数 <= 10000

【解答思路】

1. 后序遍历 + 剪枝 （从底至顶）

时间复杂度：O(N) 空间复杂度：O(N)

class Solution { public boolean isBalanced(TreeNode root) { return recur(root) != -1; } private int recur(TreeNode root) { if (root == null) return 0; int left = recur(root.left); if(left == -1) return -1; int right = recur(root.right); if(right == -1) return -1; return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1; } }

2. 先序遍历 + 判断深度 （从顶至底）

时间复杂度：O(NlogN) 空间复杂度：O(N)

public boolean isBalanced(TreeNode root) { if(root == null) return true; int l = maxDepth(root.left); int r = maxDepth(root.right); if(Math.abs(r-l)>1){ return false; } else{ return isBalanced(root.left) && isBalanced(root.right); } } public int maxDepth(TreeNode root) { if(root == null) return 0; return Math.max(maxDepth(root.left),maxDepth(root.right))+1; }

【总结】

1.树的遍历方式总体分为两类：深度优先搜索（DFS）、广度优先搜索（BFS）；

常见的 DFS ： 先序遍历、中序遍历、后序遍历； 常见的 BFS ： 层序遍历（即按层遍历）。

2.二叉树遍历

前序遍历 先输出当前结点的数据，再依次遍历输出左结点和右结点中序遍历 先遍历输出左结点，再输出当前结点的数据，再遍历输出右结点后续遍历 先遍历输出左结点，再遍历输出右结点，最后输出当前结点的数据

3. 审题 任意节点 遍历所有情况 切忌想当然

转载链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/solution/mian-shi-ti-55-ii-ping-heng-er-cha-shu-cong-di-zhi/