标签: binary-tree

什么是最简单的方法,最好是使用递归,在BST(二进制搜索树)中找到最短的根到叶路径.Java首选,伪代码没关系.

谢谢!

计算两个节点之间的最长路径.
路径是拱形的.
签名方法是:

public static int longestPath(Node n)

在下面的示例二叉树中,它是4(通过2-3-13-5-2).

这就是我现在所拥有的,对于给定的树,它只返回0.

public static int longestPath(Node n) {
    if (n != null) {
        longestPath(n, 0);
    }
    return 0;
}
private static int longestPath(Node n, int prevNodePath) {

    if (n != null && n.getLeftSon() != null && n.getRightSon() != null) {
        int currNodePath = countLeftNodes(n.getLeftSon()) + countRightNodes(n.getRightSon());
        int leftLongestPath = countLeftNodes(n.getLeftSon().getLeftSon()) + countRightNodes(n.getLeftSon().getRightSon());
        int rightLongestPath = countLeftNodes(n.getRightSon().getLeftSon()) + countRightNodes(n.getRightSon().getRightSon());

        int longestPath = currNodePath > leftLongestPath ? currNodePath : leftLongestPath;
        longestPath = …

我在一次采访中被问到了这个问题,它让我付出了一份工作:P面试官问道,你将获得一棵树的根,你必须将根返回复制的树,但副本应该是以迭代的方式.我在这里粘贴我的代码,我在那里写了相同的,它工作正常.我最初使用两个堆栈来做这个,面试官说他不喜欢,然后我用以下方式做到了.面试官对我使用另一个包含指向原始和最终树的指针的结构有点不满(参考代码).

我想知道是否还有其他更好的方法吗？

struct node
{
   int data;
   struct node * left;
   struct node * right;
};

struct copynode
{
   node * original;
   node * final;
};

node * copy(node *root)
{
    stack <copynode*> s;
    copynode * temp=(copynode*)malloc(sizeof(copynode));
    temp->original=root;
    temp->final=(node *)malloc(sizeof(node));
    s.push(temp);
    while(s.empty()==false)
    {
       copynode * i;
       i=s.top();
       s.pop();
       i->final=i->original;
       if(i->original->left)
       {
          copynode *left=(copynode*)malloc(sizeof(copynode));
          left->original=i->original->left;
          left->final=(node *)malloc(sizeof(node));
          s.push(left);
       }
       if(i->original->right)
       {
          copynode *right=(copynode*)malloc(sizeof(copynode));
          right->original=i->original->right;
          right->final=(node *)malloc(sizeof(node));
          s.push(right);
       }
   }  
   return temp->final;
}

对于家庭作业,我写了一些scala代码,其中我有以下类和对象(用于建模二叉树):

object Tree {
  def fold[B](t: Tree, e: B, n: (Int, B, B) => B): B = t match {
    case Node(value, l, r) => n(value,fold(l,e,n),fold(r,e,n))
    case _ => e
  }
  def sumTree(t: Tree): Tree = 
    fold(t, Nil(), (a, b: Tree, c: Tree) => {
      val left = b match {
        case Node(value, _, _) => value
        case _ => 0
      }
      val right = c match {
        case Node(value, _, _) => value
        case _ => 0
      }
      Node(a+left+right,b,c) …

我想知道二叉树T2是否是二叉树T1的子树.我读到可以使用预订和有序遍历为T2和T1构建字符串表示,如果T2字符串是T1字符串的子字符串,则T2是T1的子树.

我对这种方法有点困惑,不确定它的正确性.

来自wiki:"树的子树T是由T中的节点及其T中的所有后代组成的树."

在以下示例中:

T2:
  1
 / \
2   3

T1:
  1
 / \
2   3
     \
      4

如果我们为T2和T1构建字符串:

预购T2:"1,2,3"
预购T1:"1,2,3,4"
in T2:"2,1,3
"in T1:"2,1,3,4"

T2字符串是T1的子字符串,因此使用上述子字符串匹配方法,我们应该得出结论T2是T1的子树.

但是,根据定义,T2不应该是T1的子树,因为它没有T1的根节点的所有后代.

有一个相关的讨论在这里,这似乎结束方法是正确的.

我在这里错过了什么吗？

查找二叉树最大深度深度的递归机制非常简单,但是如果没有递归,我们怎样才能有效地完成它,因为我有一个大树,我宁愿避免这种递归.

//Recursive mechanism which I want to replace with non-recursive
private static int maxDepth(Node node) {
if (node == null) return 0;
    return 1 + Math.max(maxDepth(node.left), maxDepth(node.right)); 
}

PS:我在寻找Java的答案.

我意识到泛型图上的BFS和DFS的运行时是O(n + m),其中n是节点数,m是边数,这是因为对于每个节点,必须考虑它的邻接列表.但是,当它在二叉树上执行时,BFS和DFS的运行时是什么？我认为它应该是O(n),因为可以离开节点的可能边数是恒定的(即2).请确认这是否正确理解.如果没有,那么请解释二叉树上BFS和DFS的正确时间复杂度是什么？

我访问了很多网站,但无法找到Morris postOrder遍历的任何算法.我知道我们可以在preOrder和inOrder中使用Morris算法.如果有人指向postOrder Morris算法(如果存在的话),那将会很有帮助.

我正在尝试使用红黑树实现字典.
我测试了插入方法,它似乎工作得很好,RBtree似乎保持正确的形状和颜色.执行二叉树节点删除的方法似乎是正确的,但是我在删除结束时调用的deleteFixUp方法遇到了很大的问题.

你想帮我搞清楚我做错了什么吗？当然,如果您有任何改进我的代码的建议,我们将非常感激.

RBTreeWParentDictionary.java(这里我实现了RedBlackTree)

package dictionary;

import java.util.Comparator;

public class RBTreeWParentDictionary<K, V> implements IDictionary<K, V> {
  /**
   * The root node of the RBTreeWParentDictionary
   */
  public RBTreeWParentNode<K, V> root;

  /**
   * Object used to compare two T objects.
   */
  private Comparator<K>          comparator;

  private int                    length;

  /**
   * Creates the dictionary based on red/black tree with null root
   * 
   * @param comparator
   *          The comparator for keys
   */
  public RBTreeWParentDictionary(Comparator<K> comparator) {
    this.root = null;
    this.comparator = comparator;
    this.length = 0; …

我编写了一个java例程来比较2个二叉树.我正在寻找在更短的时间内运行的更好的算法.

 public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode(int x) { val = x; }
 }

 class Solution {
  public boolean isSameTree(TreeNode p, TreeNode q) {

    if  ( p == null && q==null)
        return true;

    if (p == null || q == null) 
        return false;

    if ( (p.val == q.val) && isSameTree(p.left, q.left) && 
      isSameTree(p.right, q.right))
        return true;
    else 
        return false;  
   }   
  }

我的代码需要O(n log n)时间.

如何减少所需的时间？