标签: binary-tree

我有一个无序二叉树，我必须采取一种方法来删除根 x 的子树。如果元素 x 在二叉树中出现多次，则该方法仅删除根 x 的一个子树（它找到的第一个子树）。如果执行了删除，则返回 true。如果二叉树中不存在元素 x，则返回 false。所以方法是：

    public class BinaryTree 
{
    protected class Node 
    {
        Integer element;
        Node left;
        Node right;

        Node(int element) 
        {
            this.element = element;
            left = right = null;
        }

        Node(int element, Node left, Node right) 
        {
            this.element = element;
            this.left = left;
            this.right = right;
        }

    protected Node root;

    public BinaryTree() 
    {
        root = null;
    }

    private class BoolNode 
    {
        boolean ft;
        Node nodo;

        BoolNode(boolean ft, Node nodo) 
        {
            this.ft = ft;
            this.nodo …

路径总和
给定一个二叉树和一个总和，找出所有根到叶的路径，其中每个路径的总和等于给定的总和。
例如：总和 = 11。

    5 
   / \ 
  4   8
 /   / \ 
2  -2   1 

Run Code Online (Sandbox Code Playgroud)

答案是 ：

[
  [5, 4, 2], 
  [5, 8, -2]
]

Run Code Online (Sandbox Code Playgroud)

我个人认为，时间复杂度 = O(2^n)，n 是给定二叉树的节点数。

---

谢谢Vikram Bhat和David Grayson，紧时间复杂度 = O(nlogn)，n 是给定二叉树中的节点数。

• 算法检查每个节点一次，这导致 O(n)
• “矢量one_result（subList）；” 每次都会将整个路径从 subList 复制到 one_result，这会导致 O(logn)，因为高度是 O(logn)。
  

所以最后，时间复杂度 = O(n * logn) =O(nlogn)。

---

这个解决方案 的想法是DFS [C++]。

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode …

Run Code Online (Sandbox Code Playgroud)

我有以下形式的随机二叉树

12

13、14

29、26、89

每个节点有两个子节点，即 (12->(13, 14), 13->(29, 26), 14 ->(26, 89))。这里我需要以 [[12, 13, 29], [ 12, 13, 26], [12, 14, 26], [12, 14, 89]] 的形式返回所有可能的路径。我尝试使用以下代码。我在更新列表时遇到问题。提前致谢。

class Tree:

    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

    def __str_(self):
        return '%s' % self.data

def makeList(tree, path =[]):
    if(tree != None):
        path.append(tree.data)
        if tree.left:
            path.append(makeList(tree.left, path))
        if tree.right:
            path.append(makeList(tree.left, path))

    return path

根 = 树（12）

root.left = 树（13）

root.right = 树（14）

root.right.left = 树（26）

root.left.right = …

我已经可以在 java 中使用以下算法将数组转换为二叉树：

public class TreeNode {
    public TreeNode left, right;
    public int val;

    public TreeNode(int val) {
        this.val = val;
    }
}

public TreeNode arrayToTree(Integer[] input){
    TreeNode root = createTreeNode(input,1);
    return root;
}

private TreeNode createTreeNode(Integer[] input, int index){
    if(index<=input.length){
        Integer value = input[index-1];
        if(value!=null){
            TreeNode t = new TreeNode(value);
            t.left = createTreeNode(input, index*2);
            t.right = createTreeNode(input, index*2+1);
            return t;
        }
    }
    return null;
}

当输入为{1,null,2,null,null,3} 时，我得到以下树：

1        
 \   
  2    
 /   
3

但是我认为输入{1,null,2,3}足够清晰，可以定义像上面这样的树。

避免输入数组中定义的冗余空值有什么 …

我正在尝试在 Scala 中制作一个非常简单的二叉树，用于数据存储和遍历。

现在我有：

trait Tree
case class Node(left: Tree, value: String, right: Tree) extends Tree

我的问题：

1. 我怎样才能包含一个指向父级的指针？

2. 我可以以任何方式将左指针和右指针设置为空吗？或者根节点的父指针？

3. 我怎样才能真正遍历这棵树？

4. 更新节点的值容易吗？

有没有比使用 更快的方法来搜索数据JavaScript（特别是在V8via上node.js，但没有 c/c++ 模块）JavaScript Object？

这可能已经过时，但它表明为每个属性动态生成一个新类。这让我想知道二叉树实现是否会更快，但事实似乎并非如此。

二叉树实现不太平衡，因此平衡可能会更好（只有前 26 个值是手工粗略平衡的。）

有谁知道为什么或如何改进它？另一方面：动态类概念是否意味着实际上有大约 260,000 个属性（在第二个链接的 jsperf 基准测试中）以及随后在内存中保存的动态类定义链？

我正在解决一个名为codefights的网站上的一些问题，最后一个解决的是关于二叉树的问题，其中：

考虑一个特殊的工程师和医生家庭。这个家庭有以下规则：

每个人都有两个孩子。工程师的第一个孩子是工程师，第二个孩子是博士。医生的第一个孩子是医生，第二个孩子是工程师。一代又一代的博士和工程师都是从工程师开始的。

我们可以用这张图来表示这种情况：

            E
       /         \
      E           D
    /   \        /  \
   E     D      D    E
  / \   / \    / \   / \
 E   D D   E  D   E E   D

Run Code Online (Sandbox Code Playgroud)

给定一个人在上面祖先树中的等级和位置，找到这个人的职业。注意：在这棵树中，第一个孩子被视为左孩子，第二个孩子被视为右孩子。

由于有一些空间和时间限制，解决方案不能基于实际构建树，直到所需的级别并检查哪个元素在所要求的位置。到现在为止还挺好。我用python编写的建议解决方案是：

def findProfession(level, pos):

    size = 2**(level-1)
    shift = False    

    while size > 2:
        if pos <= size/2:
            size /= 2
        else:
            size /= 2
            pos -= size
            shift = not shift

    if pos == 1 and shift == False:
        return 'Engineer'
    if pos …

为什么通过根、左和右遍历树称为预排序？这不应该是有序的，因为根总是在第一位吗？

为什么这样称呼它对我来说没有意义，因为根始终是第一个元素。

我正在尝试写一些东西来确定二叉树的最大深度，但到目前为止只得到一件事，它不断地返回树中的节点数，而另一件事，在下面，总是或多或少一个. 经过数小时的尝试调整后，我真的可以使用一些建议..

void findthedepth(nodeoftree<node>* root, int* depthtotal, int* depthcurrent){

    int left = 0, right = 0;

    if( root == nullptr ){
        *depthtotal = 0;
        *depthcurrent = 0;
        return;
    }

    findthedepth(root->rightp(), depthtotal, depthcurrent);
    right = *depthcurrent;

    *depthcurrent = 0;

    findthedepth(root->leftp(), depthtotal, depthcurrent);
    left = *depthcurrent;


    if (left > right){ 
        *depthtotal += left + 1;
    }
    else { 
        *depthtotal += right + 1;
    }
}

Haskell初学者在这里：二叉树的中序遍历很简单，例如：

data IntegerTree = Leaf Integer
                 | Node IntegerTree Integer IntegerTree

inorder :: IntegerTree -> [Integer]
inorder (Leaf n)     = [n]
inorder (Node l n r) = inorder l ++ [n] ++ inorder r

然而，在我看来，必须有一个更有效的实现。由于列表是单链表，串联inorder l和[n]似乎浪费，特别是因为这种工作是为一棵大树进行多次。我可以通过以不同的方式编写相同的函数来避免这个问题吗？

我最初是在尝试解决以类似方式构建移动列表的河内塔难题时考虑到这一点的，我希望可以使用类似的递归算法解决许多问题。