【Leetcode二叉树】662. 二叉树最大宽度(利用父子节点pos关系求宽度，非常好的思路)

【Leetcode二叉树】662. 二叉树最大宽度(利用父子节点pos关系求宽度，非常好的思路)

文章目录

• • Leetcode662
  • • 1.问题描述
    • 2.解决方案
    • • 整体思路：
      • 解法一：用beginPos维护pos进而求宽度
      • 解法二：用ArrayList维护pos进而求宽度

Leetcode662 1.问题描述

2.解决方案 整体思路：

1.这个给每个节点一个pos值，进而封装一层的思想非常优秀
2.既能使用到pos值，又不用使用静态数组存储节点
3.即为左右指针存储树，还能使用到静态数组的特性

解法一：用beginPos维护pos进而求宽度

1.思路就是每一层的第一个节点为beginPos，后面的节点都减去beginPos，最后求最大值
2.但是leetcode有一个样例没过

class AnnotatedNode {
    TreeNode node;
    int pos;
    AnnotatedNode(TreeNode n,int p) {
        node = n;
        pos = p;
    }
}

public class lc662 {
    public int widthOfBinaryTree(TreeNode root) {
        Queue queue = new linkedList<>();
        queue.add(new AnnotatedNode(root,0));
        int max=0;
        while(queue.isEmpty()==false){
            int beginPos=Integer.MAX_VALUE;
            int len=queue.size();
            for(int i=0;i 


 
解法二：用ArrayList维护pos进而求宽度 
 
 
1.思路就是把每一层不为空的节点的pos加入数组中
 2.最后只要看数组首尾之差就是宽度了
 
 
class AnnotatedNode {
    TreeNode node;
    int pos;
    AnnotatedNode(TreeNode n,int p) {
        node = n;
        pos = p;
    }
}

public class lc662 {
    public int widthOfBinaryTree1(TreeNode root) {
        Queue queue = new linkedList<>();
        queue.add(new AnnotatedNode(root,0));
        int max=0;
        while(queue.isEmpty()==false){
            int len=queue.size();
            ArrayList posList = new ArrayList<>();
            for(int i=0;i					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5636618.html