当前位置:首页 » 面试笔试 » 正文

把二叉树打印成多行

13487 人参与  2019年03月19日 12:42  分类 : 面试笔试  评论

题目描述

从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。

image.png

image.png

void BinaryTreeLevelOrder(BTNode* root)
{
    Queue q;
    //树为空,直接返回
    if (root == NULL)
    {
        return;
    }
    QueueInit(&q);
    //先将根节点入队
    QueuePush(&q, root);
    while (QueueEmpty(&q))
    {
        //出队保存队头并访问
        BTNode* front = QueueFront(&q);
        printf("%c", front->_data);
        QueuePop(&q);
        //将出队结点的左子树根入队
        if (front->_left)
            QueuePush(&q, front->_left);
        //将出队结点的右子树根入队
        if (front->_right)
            QueuePush(&q, front->_right);
    }
}

利用递归的方法进行先序遍历,传递深度,递归深入一层扩容一层数组,先序遍历又保证了同层节点按从左到右入数组,十分巧妙!!!

他在不断地扩容,最后答案类似这样{{1},{2,3},{4,5,6}}

多传递一个当前结点所在层次就可以用前序遍历实现了,学习了

假如现在元素是[1,2,3],当进入2时会创建一个 arraylist,此时 depth = 2,size=2;当2遍历完后会进入3,此时3 就不用创建 arraylist 了,因为 2,3是同一层的,并且此时 depth==size 。这个判断是用来让最左的元素创建 arraylist 就行了,而同一层后边的元素共用这个 arraylist

利用递归的方法进行先序遍历,传递深度,递归深入一层扩容一层数组,先序遍历又保证了同层节点按从左到右入数组,十分巧妙!!!

代码实现如下:

//用递归做的
public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        depth(pRoot, 1, list);
        return list;
    }
     
    private void depth(TreeNode root, int depth, ArrayList<ArrayList<Integer>> list) {
        if(root == null) return;
        if(depth > list.size()) 
            list.add(new ArrayList<Integer>());
        list.get(depth -1).add(root.val);
         
        depth(root.left, depth + 1, list);
        depth(root.right, depth + 1, list);
    }
}

来源:我是码农,转载请保留出处和链接!

本文链接:http://www.54manong.com/?id=1233

程序员面试  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!