1. 題目

在一個 m*n 的二維字符串數組中輸出二叉樹，并遵守以下規則：

• 行數 m 應當等于給定二叉樹的高度。
• 列數 n 應當總是奇數。
• 根節點的值（以字符串格式給出）應當放在可放置的第一行正中間。
• 根節點所在的行與列會將剩余空間劃分為兩部分（左下部分和右下部分）。
• 你應該將左子樹輸出在左下部分，右子樹輸出在右下部分。
• 左下和右下部分應當有相同的大小。即使一個子樹為空而另一個非空，你不需要為空的子樹輸出任何東西，但仍需要為另一個子樹留出足夠的空間。然而，如果兩個子樹都為空則不需要為它們留出任何空間。
• 每個未使用的空間應包含一個空的字符串""。
• 使用相同的規則輸出子樹。

示例 1: 輸入:1/2 輸出: [["", "1", ""],["2", "", ""]]示例 2: 輸入:1/ \2 3\4 輸出: [["", "", "", "1", "", "", ""],["", "2", "", "", "", "3", ""],["", "", "4", "", "", "", ""]]示例 3: 輸入:1/ \2 5/ 3 / 4 輸出: [["", "", "", "", "", "", "", "1", "", "", "", "", "", "", ""]["", "", "", "2", "", "", "", "", "", "", "", "5", "", "", ""]["", "3", "", "", "", "", "", "", "", "", "", "", "", "", ""]["4", "", "", "", "", "", "", "", "", "", "", "", "", "", ""]] 注意: 二叉樹的高度在范圍 [1, 10] 中。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/print-binary-tree
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 先求二叉樹高度height
• 根據高度知道列的寬度width = 2^height - 1
• 遞歸在區間中點填入節點的val的string格式

class Solution { public:vector<vector<string>> printTree(TreeNode* root) {int height = getHeight(root);//求高度int width = (2<<(height-1))-1;//確定寬度vector<vector<string>> ans(height,vector<string> (width,""));dfs(ans,root,0,0,width-1);return ans;}int getHeight(TreeNode* root)//遞歸求高度{if(root == NULL)return 0;return max(getHeight(root->left),getHeight(root->right))+1;}void dfs(vector<vector<string>> &ans, TreeNode* root, int f, int L, int R){if(root == NULL)return;int mid = ((L+R)>>1);//區間中點ans[f][mid] = to_string(root->val);//f深度dfs(ans,root->left,f+1,L,mid-1);//遞歸填充左右側dfs(ans,root->right,f+1,mid+1,R);} };

總結

以上是生活随笔為你收集整理的LeetCode 655. 输出二叉树（二叉树高度二叉树遍历）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。