二叉树打印

秒速五厘米 2022-06-09 01:00 176阅读 0赞

**题目**

有一棵二叉树，请设计一个算法，按照层次打印这棵二叉树。

给定二叉树的根结点root，请返回打印结果，结果按照每一层一个数组进行储存，所有数组的顺序按照层数从上往下，且每一层的数组内元素按照从左往右排列。保证结点数小于等于500。

我的提交：

# -*- coding:utf-8 -*-
    
    # class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None
    class TreePrinter:
        def printTree(self, root):
            # write code here
            result = []
            queue = []
            if root == None:
                return result
            result.append([root.val])
            queue.append([root])
            while True:
                line = []
                qline = []
                parents = queue[len(result) - 1]
                for i in range(len(parents)):
                    node = parents[i]
                    if node.left != None:
                        qline.append(node.left)
                        line.append(node.left.val)
                    if node.right != None:
                        qline.append(node.right)
                        line.append(node.right.val)
    
                if len(line) == 0:
                    return result
                queue.append(qline)
                result.append(line)

参考答案：

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };*/
    
    class TreePrinter {
    public:
        vector > printTree(TreeNode* root) {
            int dep[550],head = 0,tail = 0;
            TreeNode *now,*q[550];
            q[tail ++] = root; dep[root->val] = 0;
            while(head != tail){
                now = q[head ++];
                if(now->left) q[tail ++] = now->left,dep[now->left->val] = dep[now->val] + 1;
                if(now->right) q[tail ++] = now->right,dep[now->right->val] = dep[now->val] + 1;
            }
            vector > ret;
            for(int j,i = 0;i < tail;i = j){
                vector tmp;
                j = i;
                while(j < tail && dep[q[j]->val] == dep[q[i]->val]){
                    tmp.push_back(q[j]->val);
                    ++ j;
                }
                ret.push_back(tmp);
            }
            return ret;
        }
    };