2023-06-06：給你二叉樹的根結(jié)點 root ，請你設(shè)計算法計算二叉樹的 垂序遍歷 序列。

對位于 (row, col) 的每個結(jié)點而言，

其左右子結(jié)點分別位于 (row + 1, col - 1) 和 (row + 1, col + 1)

樹的根結(jié)點位于 (0, 0) 。

二叉樹的 垂序遍歷 從最左邊的列開始直到最右邊的列結(jié)束，按列索引每一列上的所有結(jié)點，

形成一個按出現(xiàn)位置從上到下排序的有序列表。如果同行同列上有多個結(jié)點，

則按結(jié)點的值從小到大進行排序。

返回二叉樹的 垂序遍歷 序列。

輸入：root = [3,9,20,null,null,15,7]。

輸出：[[9],[3,15],[20],[7]]。

答案2023-06-06：

大體過程如下：

1 定義結(jié)構(gòu)體TreeNode表示二叉樹節(jié)點，包含屬性Val表示節(jié)點值和Left和Right分別表示左右節(jié)點。

2.定義結(jié)構(gòu)體Info表示節(jié)點信息，包含屬性row、col和val分別表示節(jié)點所在的行、列和值。

3.定義函數(shù)NewInfo()創(chuàng)建節(jié)點信息。

4.定義切片類型ByColThenRowThenVal并實現(xiàn)其三個方法Len()、Less()和Swap()使之按列、行和節(jié)點值排序。

5.定義函數(shù)verticalTraversal()實現(xiàn)二叉樹的垂序遍歷。

6.在verticalTraversal()中，創(chuàng)建切片collects存儲各節(jié)點信息，并將根節(jié)點的信息存入其中。

7.調(diào)用函數(shù)dfs()遍歷整個二叉樹，添加各節(jié)點的信息到collects中。

8.對collects按列、行和節(jié)點值排序。

9.遍歷collects，將同列的所有節(jié)點值存入一個新的子切片，將子切片添加到答案ans中。

10.返回答案ans。

時間復雜度是O(nlogn)，其中n是節(jié)點數(shù)。n個節(jié)點需要遍歷一次，排序時間復雜度是O(nlogn)。所以總時間復雜度是O(nlogn)。

空間復雜度是O(n)，其中n是節(jié)點數(shù)。需要使用切片collects來存儲節(jié)點的信息，collects的長度最大是n，所以空間復雜度是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++完整代碼如下：

#include <iostream>
#include <vector>
#include <algorithm>
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;
}

文章來源地址http://www.zghlxwxcb.cn/news/detail-473595.html

到了這里，關(guān)于2023-06-06：給你二叉樹的根結(jié)點 root ，請你設(shè)計算法計算二叉樹的 垂序遍歷 序列。 對位于 (row, col) 的每個結(jié)點而言， 其左右子結(jié)點分別位于 (row + 1, col -的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！