标签: binary-tree

约20题游戏的一个问题是问在这里:

但是,如果我正确地理解它,答案似乎就是假设每个问题都会从一个分层树上下来.如果游戏是这样的话,二叉树应该可以工作:

1. 它是动物吗？是.
2. 它是哺乳动物吗？是.
3. 它是猫吗？是.

因为猫是哺乳动物的一个例子,哺乳动物是动物的一个例子.但如果问题是这样的呢？

1. 它是哺乳动物吗？是.
2. 它是捕食者吗？是.
3. 它有长鼻子吗？没有.

你不能用这些问题分枝树,因为有很多掠食者不是哺乳动物.因此,你不能将你的程序缩小到哺乳动物的范围,让捕食者成为哺乳动物的一个子集.

那么有没有办法使用我不理解的二进制搜索树,或者是否存在针对此问题的不同算法？

只是为了澄清,我只使用了20个问题作为例子,所以我的问题一般是关于这种搜索问题,而不是20问题游戏中特别涉及的其他问题.

这是维基百科上有关BST的一些代码:

# 'node' refers to the parent-node in this case
 def search_binary_tree(node, key):
     if node is None:
         return None  # key not found
     if key < node.key:
         return search_binary_tree(node.leftChild, key)
     elif key > node.key:
         return search_binary_tree(node.rightChild, key)
     else:  # key is equal to node key
         return node.value  # found key

现在这是一个二叉树:

       10
    5        12
  3   8    9   14
     4 11  

如果我正在搜索11,并且我在那里遵循算法,我从10开始,我右转到12,然后离开到9.然后我到达树的末端而没有找到11.但是我的树中存在11 ,它只是在另一边.

你能解释一下二叉树中这个算法在树上工作的限制吗？

谢谢.

我一直在尝试为二叉搜索树编写一个递归字符串方法，该方法返回具有预定路径信息的树的多行表示。

每个节点都应以一系列<和>字符开头，这些字符显示从根到该节点的路径。我不确定如何在每个后续调用中使用由一个字符扩展的字符串前缀参数。

该方法应该能够重现此示例：

树：

     15
    /  \
   12  18
  /   /  \
 10  16  20
   \   \
   11  17

预期的打印输出：

15
<12
<<10
<<>11
>18
><16
><>17
>>20

我是递归的新手，到目前为止，经过数小时的代码弄乱之后，我的实际打印输出还不够接近：

18
<17
<10
>15
<11
>12
16
20

这是我的树节点类，可以正常工作：

/**
 * A single binary tree node.
 * <p>
 * Each node has both a left or right child, which can be null.
 */
public class TreeNode<E> {

  private E data;
  private TreeNode<E> left;
  private TreeNode<E> right;

  /**
   * Constructs a new …

对于在函数下关闭的集合,有一种明确的方法可以将二进制递归转换为尾递归,即为Fibonacci序列添加整数:

(使用Haskell)

fib :: Int -> Int
fib n = fib' 0 1 n

fib' :: Int -> Int -> Int
fib' x y n
    | n < 1 = y  
    | otherwise = fib' y (x + y) (n - 1)

这工作,因为我们有我们的期望值y,而我们的操作,x + y其中x + y返回一个整数,就像y做.

但是,如果我想使用未在函数下关闭的集合,该怎么办？我想采用一个将列表拆分为两个列表的函数,然后对这两个列表执行相同的操作(例如递归创建二叉树),当另一个函数神奇地说明何时停止查看结果分割时,我停止:

[1, 2, 3, 4, 5] -> [[1, 3, 4], [2, 5]] -> [[1, 3], [4], [2], [5]]

那是,

splitList :: [Int] -> [[Int]]
splitList …

我正在解决一个问题,我必须在二叉树中找到最长的叶子到叶子的路径及其长度.

例如,如果二叉树如下:

         a
         /\
        b c
      /   / \
     d   e  f 
    / \      \
   g  h      p
       \
        k

最长的叶到叶路径是khdbacfp,长度为8.

我通过递归地找到左和右子树的长度然后计算长度return height_left + height_right + 1.我的观念是否正确？

另外我应该如何打印最长的叶到叶路径？我只是想要一个想法继续下去.

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

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

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

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

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

我最好的猜测是,当您从已经平衡的AVL树插入或删除一个元素时,一次旋转总是足以平衡AVL树.

一次轮换总是足够吗？一个例子将有助于需要多次轮换.

PS:我将RL/LR旋转计为仅一次旋转.

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

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>(); …

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

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

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

我正在努力解决这个问题,我想以非递归的方式解决这个问题.我的算法似乎没有逻辑错误,73%的测试用例通过了.但它无法处理大数据,报告称"超出时间限制".我很感激,如果有人能给我一些提示,如何在非递归中做到这一点,并避免时间限制超过,提前谢谢!

问题链接

我相信在LeetCode中也有类似的一个.

http://www.lintcode.com/en/problem/binary-tree-maximum-path-sum-ii/

问题描述:

给定二叉树,从根找到最大路径总和.路径可以在树中的任何节点处结束,并且其中包含至少一个节点.

例:

鉴于以下二叉树:

1

/ \

2 3

返回4.(1-> 3)

法官

超出时限

总运行时间:1030毫秒

输入 输入数据

{-790,-726,970,696,-266,-545,830,-866,669,-488,-122,260,116,521,-866,-480,-573,-926,88,733,#,#,483,-935,-285,-258,892,180,279 ,-935,675,2,596,5,50,830,-607,-212,663,25,-840,#,#, - 333754,#817842,-220,-269,9,-862,-78,-473,643,536 - 142,773,485,262,360,702,-661,244,-96,#519566,-893,-599,126,-314,160,358,159,#,#, - 237,-522,-327,310,-506,462,-705,868,-782,300,-945,-3,139, - 193,-205,-92,795,-99,-983,-658,-114,-706,987,292,#,234,-406,-993,-863,859,875,383,-729,-748,-258,329,431,-188,-375 ,-696,-856,825,-154,-398,-917,-70,105,819,-264,993,207,21,-102,50,569,-824,-604,895,-564,-361,110,-965,-11,557,#,202213 ,-141,759,214,207,135,329,15,#,#,244#,334628509627,-737,-33,-339,-985,349,267,-505,-527,882,-352,-357,-630,782,-215,-555,132, - 835,-421,751,0,-792,-575,-615,-690,718,248,882,-606,-53,157,750,862,#,940,160,47,-347,-101,-947,739,894,#, - 658,-90,-277 ,-925,997,862,-481,-83,708,706,686,-542,485,517,-922,978,-464,-923,710,-691,168,-607,-888,-439,499,794,-601,435,-114,-337,422,#, - 855,-859,163 ,-224 ,902,#,577,#, - 386,272,-9 ......

预期

6678

我的代码 C++

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL; …