LeetCode学习计划：LeetCode 75-Level-2

226. 翻转二叉树

问题描述

给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例

解题思路

交换每个结点的左右子节点即可。

代码示例（JAVA）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        recursion(root);
        return root;
    }

    public void recursion(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        recursion(root.left);
        recursion(root.right);
    }
}

110. 平衡二叉树

问题描述

给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

示例

解题思路

自底而上的递归，如果子树已经不是平衡的二叉树，那么这个二叉树就不是平衡的二叉树。

代码示例（JAVA）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return validBalance(root) != null;
    }

    public Integer validBalance(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Integer leftHeight = validBalance(root.left);
        if (leftHeight == null) {
            return null;
        }
        Integer rightHeight = validBalance(root.right);
        if (rightHeight == null || Math.abs(leftHeight - rightHeight) > 1) {
            return null;
        }
        return Math.max(leftHeight, rightHeight) + 1;
    }
}