2023-06-06：給你二叉樹的根結(jié)點(diǎn) root ，請(qǐng)你設(shè)計(jì)算法計(jì)算二叉樹的 垂序遍歷 序列。
2023-06-06：給你二叉樹的根結(jié)點(diǎn) root ，請(qǐng)你設(shè)計(jì)算法計(jì)算二叉樹的 垂序遍歷 序列。
對(duì)位于 (row, col) 的每個(gè)結(jié)點(diǎn)而言，
其左右子結(jié)點(diǎn)分別位于 (row + 1, col - 1) 和 (row + 1, col + 1)
樹的根結(jié)點(diǎn)位于 (0, 0) 。
二叉樹的 垂序遍歷 從最左邊的列開始直到最右邊的列結(jié)束，按列索引每一列上的所有結(jié)點(diǎn)，
形成一個(gè)按出現(xiàn)位置從上到下排序的有序列表。如果同行同列上有多個(gè)結(jié)點(diǎn)，
則按結(jié)點(diǎn)的值從小到大進(jìn)行排序。
返回二叉樹的 垂序遍歷 序列。
輸入：root = [3,9,20,null,null,15,7]。
輸出：[[9],[3,15],[20],[7]]。
答案2023-06-06：
大體過程如下：
1 定義結(jié)構(gòu)體TreeNode表示二叉樹節(jié)點(diǎn)，包含屬性Val表示節(jié)點(diǎn)值和Left和Right分別表示左右節(jié)點(diǎn)。
2.定義結(jié)構(gòu)體Info表示節(jié)點(diǎn)信息，包含屬性row、col和val分別表示節(jié)點(diǎn)所在的行、列和值。
3.定義函數(shù)NewInfo()創(chuàng)建節(jié)點(diǎn)信息。
4.定義切片類型ByColThenRowThenVal并實(shí)現(xiàn)其三個(gè)方法Len()、Less()和Swap()使之按列、行和節(jié)點(diǎn)值排序。
5.定義函數(shù)verticalTraversal()實(shí)現(xiàn)二叉樹的垂序遍歷。
6.在verticalTraversal()中，創(chuàng)建切片collects存儲(chǔ)各節(jié)點(diǎn)信息，并將根節(jié)點(diǎn)的信息存入其中。
7.調(diào)用函數(shù)dfs()遍歷整個(gè)二叉樹，添加各節(jié)點(diǎn)的信息到collects中。
8.對(duì)collects按列、行和節(jié)點(diǎn)值排序。
9.遍歷collects，將同列的所有節(jié)點(diǎn)值存入一個(gè)新的子切片，將子切片添加到答案ans中。
10.返回答案ans。
時(shí)間復(fù)雜度是O(nlogn)，其中n是節(jié)點(diǎn)數(shù)。n個(gè)節(jié)點(diǎn)需要遍歷一次，排序時(shí)間復(fù)雜度是O(nlogn)。所以總時(shí)間復(fù)雜度是O(nlogn)。
空間復(fù)雜度是O(n)，其中n是節(jié)點(diǎn)數(shù)。需要使用切片collects來存儲(chǔ)節(jié)點(diǎn)的信息，collects的長(zhǎng)度最大是n，所以空間復(fù)雜度是O(n)。
golang完整代碼如下：
package?main
import?(
????"fmt"
????"sort"
)
type?TreeNode?struct?{
????Val???int
????Left??*TreeNode
????Right?*TreeNode
}
type?Info?struct?{
????row?int
????col?int
????val?int
}
func?NewInfo(r,?c,?v?int)?Info?{
????return?Info{row:?r,?col:?c,?val:?v}
}
type?ByColThenRowThenVal?[]Info
func?(bc?ByColThenRowThenVal)?Len()?int?{?return?len(bc)?}
func?(bc?ByColThenRowThenVal)?Less(i?int,?j?int)?bool?{
????if?bc[i].col?!=?bc[j].col?{
????????return?bc[i].col?<?bc[j].col
????}
????if?bc[i].row?!=?bc[j].row?{
????????return?bc[i].row?<?bc[j].row
????}
????return?bc[i].val?<?bc[j].val
}
func?(bc?ByColThenRowThenVal)?Swap(i?int,?j?int)?{?bc[i],?bc[j]?=?bc[j],?bc[i]?}
func?verticalTraversal(root?*TreeNode)?[][]int?{
????collects?:=?make([]Info,?0,?1000)
????rootInfo?:=?NewInfo(0,?0,?root.Val)
????collects?=?append(collects,?rootInfo)
????dfs(root,?rootInfo,?&collects)
????sort.Sort(ByColThenRowThenVal(collects))
????ans?:=?make([][]int,?0,?1000)
????for?i?:=?0;?i?<?len(collects);?i++?{
????????if?i?==?0?||?collects[i-1].col?!=?collects[i].col?{
????????????ans?=?append(ans,?[]int{})
????????}
????????ans[len(ans)-1]?=?append(ans[len(ans)-1],?collects[i].val)
????}
????return?ans
}
func?dfs(root?*TreeNode,?rootInfo?Info,?collects?*[]Info)?{
????if?root.Left?!=?nil?{
????????leftInfo?:=?NewInfo(rootInfo.row+1,?rootInfo.col-1,?root.Left.Val)
????????*collects?=?append(*collects,?leftInfo)
????????dfs(root.Left,?leftInfo,?collects)
????}
????if?root.Right?!=?nil?{
????????rightInfo?:=?NewInfo(rootInfo.row+1,?rootInfo.col+1,?root.Right.Val)
????????*collects?=?append(*collects,?rightInfo)
????????dfs(root.Right,?rightInfo,?collects)
????}
}
func?main()?{
????leaf7?:=?&TreeNode{7,?nil,?nil}
????leaf15?:=?&TreeNode{15,?nil,?nil}
????leaf20?:=?&TreeNode{20,?leaf15,?leaf7}
????leaf9?:=?&TreeNode{9,?nil,?nil}
????root?:=?&TreeNode{3,?leaf9,?leaf20}
????result?:=?verticalTraversal(root)
????fmt.Println(result)
}
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?{
????int?row;
????int?col;
????int?val;
????Info(int?r,?int?c,?int?v)?{
????????row?=?r;
????????col?=?c;
????????val?=?v;
????}
};
struct?InfoComparator?{
????bool?operator()?(const?Info&?o1,?const?Info&?o2)?{
????????if?(o1.col?!=?o2.col)?{
????????????return?o1.col?<?o2.col;
????????}
????????if?(o1.row?!=?o2.row)?{
????????????return?o1.row?<?o2.row;
????????}
????????return?o1.val?<?o2.val;
????}
};
void?dfs(TreeNode*?root,?Info?rootInfo,?vector<Info>&?collects)?{
????if?(root->left?!=?nullptr)?{
????????Info?leftInfo(rootInfo.row?+?1,?rootInfo.col?-?1,?root->left->val);
????????collects.push_back(leftInfo);
????????dfs(root->left,?leftInfo,?collects);
????}
????if?(root->right?!=?nullptr)?{
????????Info?rightInfo(rootInfo.row?+?1,?rootInfo.col?+?1,?root->right->val);
????????collects.push_back(rightInfo);
????????dfs(root->right,?rightInfo,?collects);
????}
}
vector<vector<int>>?verticalTraversal(TreeNode*?root)?{
????vector<Info>?collects;
????Info?rootInfo(0,?0,?root->val);
????collects.push_back(rootInfo);
????dfs(root,?rootInfo,?collects);
????sort(collects.begin(),?collects.end(),?InfoComparator());
????vector<vector<int>>?ans;
????for?(int?i?=?0;?i?<?collects.size();?i++)?{
????????if?(i?==?0?||?collects[i?-?1].col?!=?collects[i].col)?{
????????????ans.push_back(vector<int>());
????????}
????????ans.back().push_back(collects[i].val);
????}
????return?ans;
}
int?main()?{
????TreeNode*?leaf7?=?new?TreeNode(7);
????TreeNode*?leaf15?=?new?TreeNode(15);
????TreeNode*?leaf20?=?new?TreeNode(20,?leaf15,?leaf7);
????TreeNode*?leaf9?=?new?TreeNode(9);
????TreeNode*?root?=?new?TreeNode(3,?leaf9,?leaf20);
????vector<vector<int>>?result?=?verticalTraversal(root);
????for?(int?i?=?0;?i?<?result.size();?i++)?{
????????for?(int?j?=?0;?j?<?result[i].size();?j++)?{
????????????cout?<<?result[i][j]?<<?"?";
????????}
????????cout?<<?endl;
????}
????return?0;
}
