2023-06-08：給你一棵二叉樹的根節(jié)點(diǎn) root ，返回樹的 最大寬度 。 樹的 最大寬度 是
2023-06-08：給你一棵二叉樹的根節(jié)點(diǎn) root ，返回樹的 最大寬度 。
樹的 最大寬度 是所有層中最大的 寬度 。
每一層的 寬度 被定義為該層最左和最右的非空節(jié)點(diǎn)（即，兩個端點(diǎn)）之間的長度。
將這個二叉樹視作與滿二叉樹結(jié)構(gòu)相同，兩端點(diǎn)間會出現(xiàn)一些延伸到這一層的 null 節(jié)點(diǎn)，
這些 null 節(jié)點(diǎn)也計入長度。
題目數(shù)據(jù)保證答案將會在 32 位 帶符號整數(shù)范圍內(nèi)。
輸入：root = [1,3,2,5,3,null,9]。
輸出：4。
答案2023-06-09：
大體步驟如下：
該算法使用一個容器來存儲節(jié)點(diǎn)的信息，每個節(jié)點(diǎn)信息包含節(jié)點(diǎn)本身和其在滿二叉樹中的位置。
1.如果root為空，返回0，否則初始化一個變量ans來記錄最大寬度。
2.使用一個隊列queue來存儲節(jié)點(diǎn)信息，將根節(jié)點(diǎn)的信息{root,1}加入隊列。
3.循環(huán)處理隊列，每次處理一層，對于每個節(jié)點(diǎn)：
??a.pop出隊列中的節(jié)點(diǎn)信息，將該節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)cur。
??b.如果當(dāng)前節(jié)點(diǎn)是該層的第一個節(jié)點(diǎn)，則記錄其Index為left。
??c.如果當(dāng)前節(jié)點(diǎn)是該層的最后一個節(jié)點(diǎn)，則記錄其Index為right。
??d.如果當(dāng)前節(jié)點(diǎn)有左孩子，則將其左孩子信息{cur.Node.Left,cur.Index*2}加入隊列。
??e.如果當(dāng)前節(jié)點(diǎn)有右孩子，則將其右孩子信息{cur.Node.Right,cur.Index*2+1}加入隊列。
4.計算當(dāng)前層的寬度，將其記錄為max(right-left+1,ans)。
5.返回最大寬度ans。
時間復(fù)雜度：每個節(jié)點(diǎn)僅僅入隊、出隊各一次，因此時間復(fù)雜度為O(N)，其中N為樹中節(jié)點(diǎn)的數(shù)量。
空間復(fù)雜度：本算法使用了一個隊列來存儲節(jié)點(diǎn)信息，隊列中的節(jié)點(diǎn)數(shù)量不會超過兩層的節(jié)點(diǎn)數(shù)，因此空間復(fù)雜度為O(2^h)，其中h為樹的高度。如果是完全二叉樹，h=logN，空間復(fù)雜度為O(N)。
golang完整代碼如下：
package?main
import?(
????"container/list"
????"fmt"
)
type?TreeNode?struct?{
????Val???int
????Left??*TreeNode
????Right?*TreeNode
}
type?Info?struct?{
????Node??*TreeNode
????Index?int
}
func?widthOfBinaryTree(root?*TreeNode)?int?{
????if?root?==?nil?{
????????return?0
????}
????var?ans,?left,?right?int
????queue?:=?list.New()
????queue.PushBack(&Info{Node:?root,?Index:?1})
????for?queue.Len()?>?0?{
????????size?:=?queue.Len()
????????for?i?:=?0;?i?<?size;?i++?{
????????????cur?:=?queue.Front().Value.(*Info)
????????????queue.Remove(queue.Front())
????????????if?i?==?0?{
????????????????left?=?cur.Index
????????????}
????????????if?i?==?size-1?{
????????????????right?=?cur.Index
????????????}
????????????if?cur.Node.Left?!=?nil?{
????????????????queue.PushBack(&Info{Node:?cur.Node.Left,?Index:?cur.Index?*?2})
????????????}
????????????if?cur.Node.Right?!=?nil?{
????????????????queue.PushBack(&Info{Node:?cur.Node.Right,?Index:?cur.Index*2?+?1})
????????????}
????????}
????????ans?=?max(ans,?right-left+1)
????}
????return?ans
}
func?max(a,?b?int)?int?{
????if?a?>?b?{
????????return?a
????}
????return?b
}
func?main()?{
????root?:=?&TreeNode{
????????Val:?1,
????????Left:?&TreeNode{
????????????Val:?3,
????????????Left:?&TreeNode{
????????????????Val:?5,
????????????},
????????},
????????Right:?&TreeNode{
????????????Val:?2,
????????????Right:?&TreeNode{
????????????????Val:?3,
????????????????Right:?&TreeNode{
????????????????????Val:?9,
????????????????},
????????????},
????????},
????}
????fmt.Println(widthOfBinaryTree(root))
}
c++完整代碼如下：
using?namespace?std;
struct?TreeNode?{
????int?val;
????TreeNode*?left;
????TreeNode*?right;
????TreeNode()?:?val(0),?left(nullptr),?right(nullptr)?{}
????TreeNode(int?x)?:?val(x),?left(nullptr),?right(nullptr)?{}
????TreeNode(int?x,?TreeNode*?left,?TreeNode*?right)?:?val(x),?left(left),?right(right)?{}
};
struct?Info?{
????TreeNode*?node;
????int?index;
????Info(TreeNode*?n,?int?i)?:?node(n),?index(i)?{};
};
int?widthOfBinaryTree(TreeNode*?root)?{
????if?(!root)?{
????????return?0;
????}
????int?ans?=?1;
????int?leftmost_idx,?rightmost_idx;
????queue<Info>?q;
????q.push(Info(root,?1));
????while?(!q.empty())?{
????????int?level_size?=?q.size();
????????leftmost_idx?=?q.front().index,?rightmost_idx?=?q.front().index;
????????for?(int?i?=?0;?i?<?level_size;?i++)?{
????????????Info?cur?=?q.front();
????????????q.pop();
????????????leftmost_idx?=?min(leftmost_idx,?cur.index);
????????????rightmost_idx?=?max(rightmost_idx,?cur.index);
????????????if?(cur.node->left)?{
????????????????q.push(Info(cur.node->left,?cur.index?<<?1));
????????????}
????????????if?(cur.node->right)?{
????????????????q.push(Info(cur.node->right,?(cur.index?<<?1)?|?1));
????????????}
????????}
????????ans?=?max(ans,?rightmost_idx?-?leftmost_idx?+?1);
????}
????return?ans;
}
int?main()?{
????TreeNode*?root?=?new?TreeNode(1);
????root->left?=?new?TreeNode(3);
????root->right?=?new?TreeNode(2);
????root->left->left?=?new?TreeNode(5);
????root->left->right?=?nullptr;
????root->right->left?=?new?TreeNode(3);
????root->right->right?=?new?TreeNode(9);
????cout?<<?widthOfBinaryTree(root)?<<?endl;?
????return?0;
}
c語言完整代碼如下：
struct?TreeNode?{
????int?val;
????struct?TreeNode*?left;
????struct?TreeNode*?right;
};
struct?TreeNode*?newTreeNode()?{
????struct?TreeNode*?ans?=?(struct?TreeNode*)malloc(sizeof(struct?TreeNode));
????ans->val?=?0;
????ans->left?=?NULL;
????ans->right?=?NULL;
????return?ans;
};
struct?Info?{
????struct?TreeNode*?node;
????int?index;
};
int?widthOfBinaryTree(struct?TreeNode*?root)?{
????if?(!root)?{
????????return?0;
????}
????int?ans?=?1;
????int?leftmost_idx,?rightmost_idx;
????struct?Info?init?=?{?root,?1?};
????struct?Info?cur;
????struct?TreeNode*?node;
????struct?Info*?q?=?newTreeNode();
????int?head?=?0,?tail?=?0;
????q[head++]?=?init;
????while?(head?!=?tail)?{
????????int?level_size?=?head?-?tail;
????????leftmost_idx?=?q[tail].index,?rightmost_idx?=?q[tail].index;
????????for?(int?i?=?0;?i?<?level_size;?i++)?{
????????????cur?=?q[tail++];
????????????leftmost_idx?=?leftmost_idx?<?cur.index???leftmost_idx?:?cur.index;
????????????rightmost_idx?=?rightmost_idx?>?cur.index???rightmost_idx?:?cur.index;
????????????node?=?cur.node;
????????????if?(node->left)?{
????????????????q?=?(struct?Info*)realloc(q,?sizeof(struct?Info)?*?(head?+?1));
????????????????q[head++]?=?(struct?Info){?node->left,?cur.index?<<?1?};
????????????}
????????????if?(node->right)?{
????????????????q?=?(struct?Info*)realloc(q,?sizeof(struct?Info)?*?(head?+?1));
????????????????q[head++]?=?(struct?Info){?node->right,?(cur.index?<<?1)?|?1?};
????????????}
????????}
????????ans?=?max(ans,?rightmost_idx?-?leftmost_idx?+?1);
????}
????free(q);
????return?ans;
}
int?main()?{
????struct?TreeNode*?root?=?newTreeNode();
????root->val?=?1;
????root->left?=?newTreeNode();
????root->left->val?=?3;
????root->right?=?newTreeNode();
????root->right->val?=?2;
????root->left->left?=?newTreeNode();
????root->left->left->val?=?5;
????root->left->right?=?NULL;
????root->right->left?=?newTreeNode();
????root->right->left->val?=?3;
????root->right->right?=?newTreeNode();
????root->right->right->val?=?9;
????printf("%d\n",?widthOfBinaryTree(root));
????free(root->left->left);
????free(root->left);
????free(root->right->left);
????free(root->right->right);
????free(root->right);
????free(root);
????return?0;
}
