马小混

Ruby - 树的层次遍历

2019/03/19

Ruby - 树的层次遍历

队列

class TreeNode
  attr_accessor :val, :left, :right
  def initialize(val)
    @val = val
    @left = nil
    @right = nil
  end
end

def level_search(root)
  if root.nil
    return
  else
    queue = []
    queue << root.val
    cur_size = 1
    next_size = 0
    is_a_layer = true

    node = queue.shift

    while node != null do
      if !is_a_layer
        cur_size = next_size
        next_size = 0
      end

      cur_size -= 1
      print node.val.to_s + "  "

      if !node.left.nil?
        queue << node.left
        next_size += 1
      end
      if !node.right.nil?
        queue << node.right
        next_size += 1
      end

      # 换行
      if cur_size == 0
        p ""
        is_a_layer = false
      end

      node = queue.shift
    end
  end
end

public void levelTraverse(TreeNode root) {  
        if (root == null) {  
            return;  
        }  
        LinkedList<TreeNode> queue = new LinkedList<>();  
        queue.offer(root);  
        while (!queue.isEmpty()) {  
            TreeNode node = queue.poll();  
            System.out.print(node.val+"  ");  
            if (node.left != null) {  
                queue.offer(node.left);  
            }  
            if (node.right != null) {  
                queue.offer(node.right);  
            }  
        }  
    }


Show Disqus Comments

Post Directory