online advertising

Saturday, August 12, 2017

LeetCode OJ - Print Binary Tree

Problem:

Please find the problem here.

Analysis:

The height of a binary tree is easy to find. I claim that the width is simply $ 2^h - 1 $.

It is trivial for tree of height 1, for tree with height $ h + 1 $, one of the sub-tree must be of height $ h $, by induction we can assume its width is $ 2^h - 1 $, now the another side by have exactly the same width by the rules, therefore the total width is $ 2(2^h - 1) + 1 = 2^{h + 1} - 1 $. Therefore we proved my claim with induction.

Solution:

With the width, it is relatively easy to code the solution. We will do that in two passes, in the first pass, we compute the height, and therefore the width, with that, we allocate the result, and we use another pass to fill in the array.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/print-binary-tree

#include "LEET_PRINT_BINARY_TREE.h"
#include <map>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_PRINT_BINARY_TREE
{
    struct TreeNode
    {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
    class Solution
    {
    public:
        vector<vector<string>> printTree(TreeNode* root)
        {
            int height;
            getHeight(root, &height);
            int width = 0;
            for (int i = 0; i < height; i++)
            {
                width = 2 * width + 1;
            }
            vector<vector<string>> result;
            result.resize(height);
            for (int i = 0; i < height; i++)
            {
                result[i].resize(width);
            }
            fillTree(root, width, 0, 0, result);
            return result;
        }

        void getHeight(TreeNode* node, int* pHeight)
        {
            if (node == nullptr)
            {
                *pHeight = 0;
            }
            else
            {
                int leftHeight;
                int rightHeight;
                getHeight(node->left, &leftHeight);
                getHeight(node->right, &rightHeight);
                *pHeight = max(leftHeight, rightHeight) + 1;
            }
        }

        void fillTree(TreeNode* node, int width, int height, int offset, vector<vector<string>>& result)
        {
            if (node != nullptr)
            {
                ostringstream sout;
                int mid = width / 2;
                sout << node->val;
                result[height][offset + mid] = sout.str();
                fillTree(node->left, mid, height + 1, offset, result);
                fillTree(node->right, mid, height + 1, mid + 1 + offset, result);
            }
        }
    };
};

using namespace _LEET_PRINT_BINARY_TREE;

int LEET_PRINT_BINARY_TREE()
{
    Solution solution;
    TreeNode a(2);
    TreeNode b(1);
    TreeNode c(3);
    a.left = &b;
    a.right = &c;
    b.left = nullptr;
    b.right = nullptr;
    c.left = nullptr;
    c.right = nullptr;
    vector<vector<string>> result = solution.printTree(&a);
    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;
}

No comments :

Post a Comment