二叉树算法题

数据结构与算法

发布日期: 2020-04-04

文章字数: 2.2k

阅读时长: 10 分

阅读次数:

110 平衡二叉树

题目描述

给定一个二叉树，判断它是否是高度平衡的二叉树。

一棵高度平衡二叉树定义为：一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。
给定二叉树 [3,9,20,null,null,15,7]
    3
   / \
  9  20
    /  \
   15   7
返回 true 

解法1 自顶向下（暴力法）

构造一个获取当前节点最大深度的方法 depth(root) ，通过比较此子树的左右子树的最大高度差abs(depth(root.left) - depth(root.right))，来判断此子树是否是二叉平衡树。若树的所有子树都平衡时，此树才平衡。

此方法容易想到，但会产生大量重复计算，时间复杂度较高。

实现代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

复杂度分析

时间复杂度	O(nlgn)
空间复杂度	O(n)

解法2 自底向上

对二叉树做先序遍历，从底至顶返回子树最大高度，若判定某子树不是平衡树则 “剪枝” ，直接向上返回。

代码实现

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;
    } 
}

复杂度分析

时间复杂度	O(n)
空间复杂度	O(n)

在IntelliJ IDEA中测试

package com.cn.algorithm;

/**
 * @Author: cyh
 * @Description: 平衡二叉树
 **/
public class isBalancedDemo {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    /**
     * 自顶向下
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null)
            return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null)
            return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }

    /**
     * 自底向上
     * @param root
     * @return
     */
    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;
    }

    TreeNode arrayToTree(Integer[] array, int index) {
        TreeNode root = null;
        if (index < array.length) {
            Integer value = array[index];
            if (value == null) {
                return null;
            }
            root = new TreeNode(value);
            root.left = arrayToTree(array, 2*index + 1);
            root.right = arrayToTree(array, 2*index + 2);
            return root;
        }
        return root;
    }

    public static void main(String[] args) {
        isBalancedDemo demo = new isBalancedDemo();
        Integer[] arr = {3,9,20,null,null,15,7};
        TreeNode root = demo.arrayToTree(arr, 0);
        Boolean flag = demo.isBalanced(root);
        System.out.println(flag);
    }
}

输出结果：

true

543 二叉树的直径

题目描述

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
给定二叉树 [1,2,3,4,5]
              1
         / \
        2   3
       / \     
      4   5    
返回 3 

解题思路（深度优先搜索）

定义一个全局变量 res，用来记录最大直径。使用 dfs(node) 遍历所有的节点。

dfs(node) 的作用是：找出以 node 为根节点的二叉树的最大深度，将根节点的深度定义为 1。res 取值为以经过 root，左右子树的最大深度之和 leftDepth + rigthDepth。通过递归，找到 res 的最大值。

实现代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int leftDepth = dfs(node.left);
        int rightDepth = dfs(node.right);
        res = Math.max(res, leftDepth + rightDepth);
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

复杂度分析

时间复杂度	O(n)，其中 n 为二叉树的节点数
空间复杂度	O(Height)，其中 Height为二叉树的高度

由于递归函数在递归过程中需要为每一层递归函数分配栈空间，所以这里需要额外的空间且该空间取决于递归的深度，而递归的深度显然为二叉树的高度，并且每次递归调用的函数里又只用了常数个变量，所以所需空间复杂度为 O(Height)O(Height)

在IntelliJ IDEA中测试

package com.cn.algorithm;

/**
 * @Author: cyh
 * @Description: 二叉树的直径
 **/
public class DiameterOfBinaryTreeDemo {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    TreeNode arrayToTree(Integer[] array, int index) {
        TreeNode root = null;
        if (index < array.length) {
            Integer value = array[index];
            if (value == null) {
                return null;
            }
            root = new TreeNode(value);
            root.left = arrayToTree(array, 2*index + 1);
            root.right = arrayToTree(array, 2*index + 2);
            return root;
        }
        return root;
    }

    int res = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return res;
    }

    public int dfs(TreeNode node) {
        if (node == null) return 0;
        int leftDepth = dfs(node.left);
        int rightDepth = dfs(node.right);
        res = Math.max(res, leftDepth + rightDepth);
        return Math.max(leftDepth, rightDepth) + 1;
    }


    public static void main(String[] args) {
        DiameterOfBinaryTreeDemo demo = new DiameterOfBinaryTreeDemo();
        Integer[] arr = {1,2,3,4,5};
        TreeNode root = demo.arrayToTree(arr, 0);
        int r = demo.diameterOfBinaryTree(root);
        System.out.println(r);
    }
}

输出结果：

226 翻转二叉树

题目描述

翻转一棵二叉树。

输入：
     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：
     4
   /   \
  7     2
 / \   / \
9   6 3   1

解法1 递归法（深度优先遍历）

交换左右节点，然后再递归的交换左节点，右节点。

递归法

图片来源：https://leetcode-cn.com/problems/invert-binary-tree/solution/dong-hua-yan-shi-liang-chong-shi-xian-226-fan-zhua/

实现代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        // 交换左右节点
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        // 递归
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

复杂度分析

时间复杂度	O(n)，其中 n 为二叉树的节点数
空间复杂度	O(Height)，其中 Height为二叉树的高度

解法2 迭代法（广度优先遍历）

先将根节点放入到队列中，然后不断的迭代队列中的元素。对当前元素调换其左右子树的位置，然后：

判断其左子树是否为空，不为空就放入队列中

判断其右子树是否为空，不为空就放入队列中

迭代法

图片来源：https://leetcode-cn.com/problems/invert-binary-tree/solution/dong-hua-yan-shi-liang-chong-shi-xian-226-fan-zhua/

代码实现

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        //将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()) {
            //每次都从队列中拿一个节点，并交换这个节点的左右子树
            TreeNode tmp = queue.poll();
            TreeNode left = tmp.left;
            tmp.left = tmp.right;
            tmp.right = left;
            //如果当前节点的左子树不为空，则放入队列等待后续处理
            if(tmp.left!=null) {
                queue.add(tmp.left);
            }
            //如果当前节点的右子树不为空，则放入队列等待后续处理
            if(tmp.right!=null) {
                queue.add(tmp.right);
            }
        }
        //返回处理完的根节点
        return root;
    }
}

复杂度分析

时间复杂度	O(n)
空间复杂度	O(n)

在IntelliJ IDEA中测试

package com.cn.algorithm;

import java.util.*;

/**
 * @Author: cyh
 * @Description: 翻转二叉树
 **/
public class InvertTreeDemo {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    TreeNode arrayToTree(Integer[] array, int index) {
        TreeNode root = null;
        if (index < array.length) {
            Integer value = array[index];
            if (value == null) {
                return null;
            }
            root = new TreeNode(value);
            root.left = arrayToTree(array, 2*index + 1);
            root.right = arrayToTree(array, 2*index + 2);
            return root;
        }
        return root;
    }

    List<Integer> treeToArray(TreeNode root, List<Integer> list) {
        if (root == null) return null;
           list.add(root.val);

               if (root.left != null) {
                   list.add(root.left.val);
               }
               if (root.right != null) {
                   list.add(root.right.val);
               }
               treeToArray(root.left, list);
               treeToArray(root.right, list);
        return list;
    }


    /**
     * 递归法（深度优先遍历）
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        // 交换左右节点
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        // 递归
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    /**
     * 迭代法（广度优先遍历）
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        //将二叉树中的节点逐层放入队列中，再迭代处理队列中的元素
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()) {
            //每次都从队列中拿一个节点，并交换这个节点的左右子树
            TreeNode tmp = queue.poll();
            TreeNode left = tmp.left;
            tmp.left = tmp.right;
            tmp.right = left;
            //如果当前节点的左子树不为空，则放入队列等待后续处理
            if(tmp.left!=null) {
                queue.add(tmp.left);
            }
            //如果当前节点的右子树不为空，则放入队列等待后续处理
            if(tmp.right!=null) {
                queue.add(tmp.right);
            }
        }
        //返回处理完的根节点
        return root;
    }

    public static void main(String[] args) {
        InvertTreeDemo demo = new InvertTreeDemo();
        Integer[] arr = {4,2,7,1,3,6,9};
        TreeNode root = demo.arrayToTree(arr, 0);
        TreeNode invertTree = demo.invertTree(root);
        List<Integer> list = new ArrayList<>();
        list = demo.treeToArray(invertTree, list);
        System.out.println(list);
    }
}

输出结果：

[4, 7, 2, 7, 9, 6, 9, 6, 2, 3, 1, 3, 1]

leetcode 树