Leetcode P620 DFS解法，思路简单易懂

Leetcode P620

思路

​ 为每个节点设置id，根节点的id为0，每个节点的左节点的id为，当前节点的id *2，右节点的id为id *2+1.

​ 那么每层 的距离就为当前节点的id - 当层节点的最小id+1.

class Solution {
   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;
       }
    }

    List<Long> list = new ArrayList<>();
    int res = 0;
    public int widthOfBinaryTree(TreeNode root) {
        dfs(root,0,0);
        return res;
    }

    public void dfs(TreeNode root,int d,long id){
       if (root == null){
           return ;
       }
       if (list.size() == d){
           list.add(id);
       }

        res = Math.max((int) (id - list.get(d) + 1),res);

       dfs(root.left,d+1,id * 2);
       dfs(root.right,d+1,id*2+1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35