标签: binary-tree

UPDATE

我制定了一个我认为在O(n*k)运行时运行的算法.下面是伪代码:

routine heaviestKPath( T, k )

    // create 2D matrix with n rows and k columns with each element = -?
    // we make it size k+1 because the 0th column must be all 0s for a later 
    // function to work properly and simplicity in our algorithm
    matrix = new array[ T.getVertexCount() ][ k + 1 ] (-?);

    // set all elements in the first column of this matrix = 0
    matrix[ n ][ 0 ] = 0; …

如何逐级打印二叉树？

这是我今天得到的一个面试问题.果然,使用BFS风格肯定会奏效.但是,后续问题是:如何使用常量内存打印树？(所以不能使用队列)

我想过以某种方式将二叉树转换为链表但没有提出具体的解决方案.

有什么建议？

谢谢

我们有一个仅由0和1组成的二叉树(不是BST).我们需要找到最深的1,其中一条路径只由1组成

资料来源:亚马逊采访问:

给定两个二叉搜索树,按时间复杂度O(n)和空间复杂度按升序打印节点:O(1)

树木无法修改.只允许遍历.

我面临的问题是O(1)空间解决方案.如果没有这种限制,它可以很容易地解决.

我有一个完美的二叉树,即树中的每个节点都是叶节点,或者有两个子节点,并且所有叶节点都在同一级别上.每个节点都有一个深度优先的索引.

(例如,在具有3个级别的树中,根节点具有索引0,第一个孩子具有1,第一个孩子的第一个孩子具有2个,第一个孩子的第二个孩子具有3个,第二个孩子具有4个,第一个孩子第二个孩子有5个,第二个孩子的第二个孩子有6​​个.

      0
    /   \
  1      4
 / \    / \
2   3  5   6

)

我知道树的大小(节点数/最大级别),但只知道特定节点的索引,我需要计算它的级别(即它与根节点的距离).我如何最有效地完成这项工作？

考虑具有以下属性的二叉树:

1. 如果内部节点(非叶节点)有两个子节点,则其值为1.
2. 叶节点的值为0,因为它没有子节点.

树上的级别顺序遍历将生成1和0的字符串(通过在访问每个节点时打印奇怪的值).现在给定此字符串构造二叉树并在树上执行post order遍历.后订单字符串应该是程序的输出.

例如:输入字符串是111001000.从中创建二叉树.然后在树上执行post order遍历,这将导致输出:001001011

问题的"症结"是仅从级别顺序字符串创建二叉树.我该怎么做？

我正在尝试编写一个函数来计算表示为元组的树的节点.

object Main {
     def count[T](tree:Seq[T]):Int= {
        if (lst == ())
            0
        else
            count(tree(1)) + count(tree(2)) + 1
    }
     def main(args: Array[String]) {
        val lst3 = (2,(6,(8,(),()),(5,(),())),(4,(3,(),()),(10,(),())))
        println(count(lst3))
    }
}

我怎样才能在scala中实现这一点？

给定一个完美的二叉树,我需要反转交替级别:

Given tree: 
           a
        /     \
       b       c
     /  \     /  \
    d    e    f    g
   / \  / \  / \  / \
   h  i j  k l  m  n  o 

Modified tree:
           a
        /     \
       c       b
     /  \     /  \
    d    e    f    g
   / \  / \  / \  / \
  o  n m  l k  j  i  h 

我试图使用递归来执行inorder遍历并在另一个inorder遍历中修改树.

public static void reverseAltLevels(TreeNode node) {
    if (node == null)
        return;
    ArrayList<TreeNode> list = new ArrayList<TreeNode>(); …

我正在努力为以下问题找到算法:

给定一个整数的二叉树,分支(也就是从根开始并到达叶节点的分支)的成本由其值的总和给出.编写一个返回最便宜分支列表的函数.

任何人都可以向我推荐完成此练习的最简单方法吗？

在这棵树上:

     a
    / \
   b   d
  /   / \
 c   e   f
        /
       g

从根开始的最长路径是 a-d-f-g

这是我的尝试:

class Node:
  def __init__(self, x):
    self.val = x
    self.left = None
    self.right = None

def print_path(root):
  if not root:
    return []
  if root.left is None:
    return [root.val].append(print_path(root.right))
  elif root.right is None:
    return [root.val].append(print_path(root.left))
  elif (root.right is None) and (root.left is None):
    return [root.val]
  else:
    return argmax([root.val].append(print_path(root.left)), [root.val].append(print_path(root.right)))

def argmax(lst1, lst2):
  return lst1 if len(lst1) > len(lst2) else lst2

if __name__ == '__main__':
  root_node …