二叉树应用_打印二叉树

谁践踏了优雅 2022-05-22 02:46 321阅读 0赞

题目：从上往下打印二叉树的每个节点，同一层的节点按照从左往右的顺序打印。  
分析：每次打印一个节点的时候，如果该节点有子节点，就把该节点的子节点放到一个队列的末尾。每次打印队列头部的节点。直到队列中的所有节点都被打印出来为止。  
实现如下：

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };*/
    vector<int> PrintFromTopToBottom(TreeNode* root) 
    {
        vector<int> result;
        if(!root)
            return result;
        deque<TreeNode*> quetreenode;
        quetreenode.push_back(root);
        while(quetreenode.size())
        {
            TreeNode*pnode=quetreenode.front();
            quetreenode.pop_front();
            cout<<pnode->val<<",";
            result.push_back(pnode->val);
            if(pnode->left)
                quetreenode.push_back(pnode->left);
            if(pnode->right)
                quetreenode.push_back(pnode->right);
        }
        return result;
    }

题目：从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印每一层打印一行。  
分析：与上一题类似，我们可以用一个队列保存将要打印的节点，为了让每一层单独打印到一行里面，我们需要增加两个变量，一个用来保存本层要打印的节点数，一个保存下一层要打印的节点数。  
具体是如下：

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };*/
    vector<vector<int>> print(TreeNode*root)
    {
        vector<vector<int>> result;
        if(!root)
            return result;
        deque<TreeNode*> quetreenode;
        vector<int> res;
        int thislenvel=1;
        int nextlenvel=0;
        quetreenode.push_back(root);
        while(quetreenode.size())
        {
            Treenode*pnode=quetreenode.front();
            quetreenode.pop_front();
            cout<<pnode->val<<" ";
            res.push_back(pnode->val);
            if(pnode->left)
            {
                quetreenode.push_back(pnode->left);
                nextlevel++;
            }
            if(pnode->right)
            {
                quetreenode.push_back(pnode->right);
                nextlevel++;
            }
            --thislevel;
            if(thislevel==0)
            {
                thislevel=nextlevel;
                nextlevel=0;
                cout<<endl;
                result.push_back(res);
                res.clear();
            }
        }
        return result;
    }

题目：实现一个函数按照之字形顺序打印二叉树，第一行按照从左到右的顺序打印，第二行按照从右到左的顺序打印，第三行按照从左到右的顺序打印以此类推。  
分析：对于这种情况，我们应该分奇偶考虑。我们借助两个辅助栈（队列也可以），我们在打印某行的节点的时候，把下一层的子节点保存到相应的栈里面。当我们打印的是奇数层（左到右）的时候，下一层应该从右到左打印，我们先保存左节点再保存右节点；当我们打印偶数层（从右到左）的时候，我们应该先保存右节点再保存左节点。  
具体实现如下：

/*
    struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };*/
    //下面方法感觉一般
    vector<vector<int>> print(TreeNode*root)
    {
        vector<vector<int>> result;
        if(!root)
            return result;
        stack<Treenode*> left_to_right;
        stack<Treenode*> right_to_left;
        left_to_right.push(root);   
        while(left_to_right.size()||right_to_left.size())
        {
            vector<int> res;
            if(left_to_right.size())
            {
                while(left_to_right.size())
                {
                    TreeNode*pnode=left_to_right.top();
                    left_to_right.pop();
                    cout<<pnode->val;
                    res.push_back(pnode->val);
                    if(pnode->left)
                        right_to_left.push_back(pnode->left);
                    if(pnode->right)    
                        right_to_left.push_back(pnode->right);
                }
            }
            else
            {
                while(right_to_left.size())
                {
                    TreeNode*pnode=right_to_left.top();
                    right_to_left.pop();
                    cout<<pnode->val;
                    res.push_back(pnode->val);
                    if(pnode->right)
                        left_to_right.push_back(pnode->right);
                    if(pnode->left)
                        left_to_right.push_back(pnode->left);
                }
            }
            cout<<endl;
            result.push_back(res);
        }
        return result;
    }
    
    //好一点的方法,用一个stack<TreeNode*> levels[2]存
    vector<vector<int>> print(TreeNode*root)
    {
        vector<vector<int>> result;
        if(!root)
            return result;
        stack<TreeNode*> levels[2];
        int current=0;
        int next=1;
        vector<int> res;
        while(levels[0],size()||levels[1].size())
        {
            TreeNode*pnode=levels[current].top();
            levels[current].pop();
            cout<<pnode->val;
            res.push_back(pnode->val);
            if(current==0)
            {
                if(pnode->left)
                    levels[next].push_back(pnode->left);
                if(pnode->right)
                    levels[next].push_back(pnode->right);
            }
            else
            {
                if(pnode->right)
                    levels[next].push_back(pnode->right);
                if(pnode->left)
                    levels[next].push_back(pnode->left);
            }
    
            if(levels[current].empty())
            {
                current=1-current;
                next=1-next;
                result.push_back(res);
                cout<<endl;
                res.clear();
            }       
        }
        return result;
    }