在二叉树java中找到最右边的孩子

Question

我在二叉树中找到最后一个元素(最右边的孩子)时遇到了一些麻烦.

这是我到目前为止:

public Node findLastElement(Node root) {
  Node x = root;
  if (x != null)
      findLastElement(x.right);
  return x;
}

如果我打印元素,打印的最后一个元素是最后一个元素,但我似乎无法"获得"该元素.当我尝试在循环后返回x时,我得到一个nullpointer.如何保存最后一个元素并将其返回？

Answer 1

您可以递归地获取最右边的元素:

public Node findLastElement(Node root) {
    if (root == null) {
        return null;
    }
    if (root.right == null) {
        return root;
    }
    return findLastElement(root.right);
}

你也可以迭代地做.迭代通常在内存方面更好,因为它没有使用递归创建的额外堆栈帧.

public Node findLastElement(Node root) {
    if(root == null) {
        return null;
    }
    Node x = root;
    while(x.right != null) {
        x = x.right;
    }
    return x;
}

并且不需要临时变量x.由于java通过值传递引用(它们是原始引用的副本),因此我们对输入参数进行的任何赋值root都是本地的,并且不会反映在findLastElement方法之外.

public Node findLastElement(Node root) {
    if(root == null) {
        return null;
    }
    while(root.right != null)
        root = root.right;
    return root;
}