把二叉树打印成多行

题目描述

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