相关疑难解决方法(0)

这个问题可能已经过时了,但我想不出答案.

比如,有两个不同长度的列表,在某一点合并 ; 我们怎么知道合并点在哪里？

条件:

1. 我们不知道长度
2. 我们应该只解析每个列表一次.

我在一次模拟采访中遇到了一个问题,我必须找到一个二进制树在一个给定节点已经着火后完全烧毁多久.

"从一个叶子节点开始刻录二进制树.从一个节点到另一个节点刻录的时间是多少？整个树被烧毁的时间是什么？火将从一个节点传播到所有路径. "

假设你有一棵这样的树,其中N是着火的节点.这发生在第一秒,其中秒是s,所以在第0秒:

           1
       /       \
      1          1
    /  \          \
   1    1          1
      /   \         \
     1     N         1
                      \
                       1

经过一秒钟后,将使用更多刻录的节点更新树.下一秒(s + 1)的示例将如下所示:

           1
       /       \
      1          1
    /  \          \
   1    N          1
      /   \         \
     1     N         1
                      \
                       1

下一秒(s + 2)的示例将是这样的:

           1
       /       \
      N          1
    /  \          \
   1    N          1
      /   \         \
     N     N         1
                      \
                       1  

现在在第三秒(s + 3)将是这样的:

           N
       /       \
      N          1
    /  \          \
   N    N …

我有一个数据结构作业,除了常规的AVL树函数,我还要添加一个函数,它返回AVL树中任意两个数字之间的最小间隙(AVL中的节点实际上代表数字.)

假设我们在AVL树中有数字(作为节点)1 5 12 20 23 21,该函数应该返回任意两个数字之间的最小间隙.在这种情况下它应该返回"1",即| 20-21 | 或| 21-20 |.

它应该在O(1)中完成.

试图思考很多,我知道有一个伎俩但是找不到它,我已经花了好几个小时.

还有另一项任务是找到最大间隙,这很容易,它是最小和最大数之间的差异.

我在一次采访中向我询问了这个问题:我有一个二叉树,我必须找到共同的祖先(父)给出该树的两个随机节点.我也得到了一个指向根节点的指针.

我的回答是:

分别遍历两个节点的树,直到到达预期的节点.遍历时并行存储元素和链接列表中的下一个地址.然后我们有两个链接列表.因此,尝试比较两个链表,两个链表中的最后一个公共节点是父列表.

我认为这个解决方案是正确的,如果我错了,请纠正我.如果这个解决方案是正确的,我可能知道这是这项任务的唯一更好的解决方案还是有比这更好的解决方案!

我遇到了以下实现并花了一些时间,但仍然无法掌握这个想法.有人可以逐行解释它在做什么吗？我只是不明白在什么时候它可以决定一个节点是一个祖先.

谢谢

public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q)  return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null)   return root;
        return left != null ? left : right;
    }
}

可能重复:
如何在二叉树中找到两个节点的共同祖先？
二叉树的第一个共同祖先

我有一个二叉树如下.我需要找到最不常见的祖先(LCA).例如,6和4的LCA是1,4和5的LCA是2.

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

任何人都可以建议我应该如何处理和解决这个问题？