欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode Maximum Width of Binary Tree

程序员文章站 2024-02-12 22:19:28
...

题目描述:

Given a binary tree, write a function to get the maximum width of the given tree. The width of a tree is the maximum width among all levels. The binary tree has the same structure as a full binary tree, but some nodes are null.

The width of one level is defined as the length between the end-nodes (the leftmost and right most non-null nodes in the level, where the null nodes between the end-nodes are also counted into the length calculation.

leetcode Maximum Width of Binary Tree

leetcode Maximum Width of Binary Tree


题解:参考leetcode上的代码,有点小收获,记录一下自己的理解

首先我们对树中节点按照数组存储形式标号,根节点标号为1,它的左右节点标号分别为2,3。如果有一个节点标号为n,则其左右节点标号分别为2*n,2*n+1;

然后dfs按先序遍历树中节点,定义两个数组start,end,start用来 记录每层最左节点标号,end用来记录每层最右节点标号。end数组会随着遍历节点的过程不断变化。


代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
class Solution {
   
    public int widthOfBinaryTree(TreeNode root) {
          ArrayList<Integer> start=new ArrayList<>();
          ArrayList<Integer> end=new ArrayList<>();
          return dfs(root,0,1,start,end);
    }
    
    public int dfs(TreeNode root,int level,int order,List<Integer> start,List<Integer> end){
        if(root==null){
            return 0;
        }
        if(start.size()==level){
            start.add(order);
            end.add(order);
        }
        end.set(level,order);
        int cur=end.get(level)-start.get(level)+1;
        int left=dfs(root.left,level+1,2*order,start,end);
        int right=dfs(root.right,level+1,2*order+1,start,end);
        return Math.max(cur,Math.max(left,right));
    }
}