从上到下打印二叉树,将二叉树打印成多行代码实现和思路

KLQ 2020-04-14 10:29:07 java常见问答 7024

你知道从上往下打印二叉树的实现方法吗?很多人都不大了解,下面就一起来看一下,从上到下打印二叉树的实现和思路吧。

题目:

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

每一层输出一行。

思路1:(最简洁的答案)
代码实现:

//用递归做的
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);
    }
}

以上的这种方式是非常简洁的,大家可以参考一下。

思路2:

代码实现:

层次遍历
class Solution
{
    public:
        vector < vector < int > > Print(TreeNode * pRoot)
        {
            vector < vector < int > > vec;
            if (pRoot == NULL) return vec;
            queue < TreeNode * > q;
            q.push(pRoot);
            while (!q.empty())
            {
                int lo = 0, hi = q.size();
                vector < int > c;
                while (lo++ < hi)
                {
                    TreeNode * t = q.front();
                    q.pop();
                    c.push_back(t - > val);
                    if (t - > left) q.push(t - > left);
                    if (t - > right) q.push(t - > right);
                }
                vec.push_back(c);
            }
            return vec;
        }
};

以上的这种方式也是非常的简洁,大家同样可以采纳。

思路3:(思路清晰,注释详尽)

按照层次输出二叉树

访问根节点,并且将根节点入队。

当队列不空时,重复下面的操作。

弹出一个元素。作为当前的根节点。

假如,根节点有左孩子,那么,访问左孩子,将左孩子入队。

假如,根节点有右孩子,那么,访问右孩子,将右孩子入队。

代码实现:

package Tree;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/**
 * 从上到下按层打印二叉树,同一层结点从左至右输出。每一层输出一行。
 * 思路:
 * 按层次输出二叉树
 * 访问根节点,并将根节点入队。
 * 当队列不空的时候,重复以下操作。
 * 1、弹出一个元素。作为当前的根节点。
 * 2、如果根节点有左孩子,访问左孩子,并将左孩子入队。
 * 3、如果根节点有右孩子,访问右孩子,并将右孩子入队。
 */
public class Solution8
{
    public static void main(String[] args)
    {
        int[] array = {
            1
            , 2
            , 3
            , 4
            , 5
            , 6
            , 7
            , 8
            , 9
        };
        Solution8 solution8 = new Solution8();
        TreeNode treeNode = solution8.createBinaryTreeByArray(array, 0);
        for (ArrayList list:
            solution8.Print(treeNode))
        {
            System.out.println(list);
        }
    }
    /**
     * 层次遍历
     *
     * @param pRoot 根节点
     * @return arrayLists
     */
    ArrayList < ArrayList < Integer >> Print(TreeNode pRoot)
    {
        //存放结果
        ArrayList < ArrayList < Integer >> arrayLists = new ArrayList < > ();
        if (pRoot == null)
        {
            return arrayLists;
        }
        //使用队列,先进先出
        Queue < TreeNode > queue = new LinkedList < > ();
        //存放每行的列表
        ArrayList < Integer > arrayList = new ArrayList < > ();
        //记录本层打印了多少个
        int start = 0;
        //记录下层打几个
        int end = 1;
        queue.add(pRoot);
        while (!queue.isEmpty())
        {
            TreeNode temp = queue.remove();
            //添加到本行的arrayList
            arrayList.add(temp.val);
            start++;
            //每打印一个节点,就把此节点的下一层的左右节点加入队列,并记录下一层要打印的个数
            if (temp.left != null)
            {
                queue.add(temp.left);
            }
            if (temp.right != null)
            {
                queue.add(temp.right);
            }
            //判断本层打印是否完成
            if (start == end)
            {
                //此时的queue中存储的都是下一层的节点,则end即为queue大小
                end = queue.size();
                start = 0;
                //把arrayList添加到结果列表arrayLists中
                arrayLists.add(arrayList);
                //重置arrayList
                arrayList = new ArrayList < > ();
            }
        }
        return arrayLists;
    }
    private TreeNode createBinaryTreeByArray(int[] array, int index)
    {
        TreeNode tn = null;
        if (index < array.length)
        {
            int value = array[index];
            tn = new TreeNode(value);
            tn.left = createBinaryTreeByArray(array, 2 * index + 1);
            tn.right = createBinaryTreeByArray(array, 2 * index + 2);
            return tn;
        }
        return tn;
    }
    public class TreeNode
    {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val)
        {
            this.val = val;
        }
    }
}

以上的三种代码实现方式和思路大家都了解了吗?除了以上的三种方式之外,还有很多方式是可以实现的呢,更多相关Java实例,可以继续的来本站了解哦