leetcode balanced binary tree(看不懂...)-白红宇

leetcode balanced binary tree(看不懂...)

阅读量：4137 次

发布时间：2019-05-25

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

http://www.cnblogs.com/Antech/p/3705928.html

问题：给一个二叉树，写一个算法判断这个树是不是balanced。

Solution #1.

第一次遇到这个问题时我的解法，如下：

public class Solution {    public boolean isBalanced(TreeNode root) {        if(root == null){            return true;        }                int depthOfLeft = getDepth(root.left, 1);        int depthOfRight = getDepth(root.right, 1);                if(Math.abs(depthOfRight-depthOfLeft) > 1){            return false;        }else{            return isBalanced(root.left) && isBalanced(root.right);        }    }        private int getDepth(TreeNode tree, int currentDepth){        if(tree == null){            return currentDepth;        }        return Math.max(getDepth(tree.left, currentDepth+1),                 getDepth(tree.right, currentDepth+1));    }}

写了一个getDepth()函数，访问每个节点都要调用一次这个函数。这个Solution也通过了leetcode的验证程序，但是后来想了想，I can do better.

下面是我对此算法时间复杂度的分析，当整棵树有N个节点时，时间复杂度是O(N*logN).

Solution #2:

今天我想出了更好的Solution，只需一遍DFS，可以将时间复杂度优化到O(N)，但是空间复杂度同样是O(N).

public class CheckTreeBalanced {        HashMap
    
      heights = new HashMap
     
      ();    // The idea is to run DFS once    boolean isBalanced(TreeNode root){        if(root == null){            heights.put(null, 0);            return true;        }                if( isBalanced(root.left) && isBalanced(root.right) ){            if(Math.abs(heights.get(root.left) - heights.get(root.right)) > 1){                return false;                            }else{                int currentHeight = Math.max(heights.get(root.left),                        heights.get(root.right)) + 1;                heights.put(root, currentHeight);                return true;            }                    }else{            return false;        }    }}

Solution #3:

Cracking the coding interview上看到另一种解法，time complexity O(N), space complexity O(logN). 之所以占用logN的空间是因为这是DFS的特点，整棵树的高度H=logN，DFS必然会占用O(H), explicitly or implicitly.

该算法的思路是基于Solution #1的一种改进，把每个节点的height信息和isBalanced信息融合到一起个变量中：

如果该变量>=0，那么该节点是balanced并且该变量就是节点的height；

如果该变量<0，那么该节点是unbalanced，但同时我们失去了它的height信息。

public class CheckTreeBalanced2 {        public int checkHeight(TreeNode root){        if(root == null){            return 0;        }                int leftHeight = checkHeight(root.left);        if(leftHeight == -1){            return -1;        }                int rightHeight = checkHeight(root.right);        if(rightHeight == -1){            return -1;        }                int heightDiff = leftHeight - rightHeight;        if(Math.abs(heightDiff) > 1){            return -1;        }else{            return Math.max(leftHeight, rightHeight);        }    }        public boolean isBalance(TreeNode root){        if(checkHeight(root) == -1){            return false;        }else{            return true;        }    }}

你可能感兴趣的文章