平衡二叉树【leetcode - 110 - 简单】

刺骨的言语ヽ痛彻心扉 2022-03-30 14:22 190阅读 0赞

胡扯：这个题做的时间还是比较长的，虽然只是一个简单题。不过在做的过程中一直觉得自己可以做出来的。哈哈，最后代码不是很好，只打败百分之36的人，这也是想到的，毕竟写了两次DFS和递归，代码不慢才怪，但是比较好理解。

## 思路： ##

1、日常非空判断。

2、先前序遍历每一个节点 [三种遍历][Link 1]

3、在每一个节点的时候，再去遍历以它为根节点的左右长度。

4、比较它的左右长度，看看是否相差1，如果不是立马终止程序，返回false

代码：代码中有一句注释，你可以打开，上面标识着每一个节点的左右长度

class Solution {
        
        boolean flag = true;
        int max = 0;
        void Preorder (TreeNode root){
            max = 0;
            dfs(root.left,1);
            int tem = max;
            max = 0;
            dfs(root.right,1);
            // System.out.println(root.val + " : " + tem + " "+max);
            if (Math.abs(tem - max) > 1){
                flag = false;
                return;
            }
    
            if( root.left != null )
                Preorder(root.left);
            if( root.right != null )
                Preorder(root.right);
        }
    
        void dfs (TreeNode root, int num){
    
            if (root == null)
                return;
            if (num > max)
                max = num;
            if( root.left != null )
                dfs(root.left,num + 1);
            if( root.right != null )
                dfs(root.right, num + 1);
        }
        
        public boolean isBalanced(TreeNode root) {
            if( root == null )
                return true;
            
            Preorder(root);
                
            return flag;
        }
    }

[Link 1]: https://blog.csdn.net/Tomwildboar/article/details/85717842