在Java中查找二叉树的最右边的子节点

Question

我在查找二叉树中最后一个元素（最右边的子节点）时遇到了一些问题。

这是我目前的代码：

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

如果我打印这些元素，最后一个被打印的是最后一个元素，但是我似乎无法"获取"该元素。当我尝试在循环后返回x时，我得到了一个nullpointer。如何保存最后一个元素并返回它？

- user16655

---

所谓的“最后一个元素”必须基于某种遍历顺序；否则它就没有意义。这是中序遍历的最后一个元素。 - Tony

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;
}

- nem035

Answer 2

你需要返回递归函数调用的结果。

例如：

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

- Trevor Freeman

---

太好了，谢谢！现在我看到正确的代码，一切都很合乎逻辑。 - user16655

@maszter 简单修复... javadoc @throws 如果节点为空，则抛出 NPE。;-) - Trevor Freeman

是的，但这是不好的实践，不是吗？ - maszter

Answer 3

如果使用null参数调用方法，则需要对x进行额外的检查。

public Node findLastElement(Node root) {
  Node x = root;

  if (x != null && x.right != null) {
      return findLastElement(x.right);
  } else {
      return x;
  }

}

- Maciej Szumielewicz

---

在第一次调用时检查传递的空参数。 - Maciej Szumielewicz

Answer 4

你需要检查当前节点和最右边的节点是否都非空，这将处理第一个传递的节点为空的情况。

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

- Abhinav

Answer 5

我更喜欢在简单的方法中使用单个返回语句，这样看起来会更清晰：

public Node findLastElement(Node root) {
    return root != null && root.right != null ? findLastElement(root.right) : root;
}

- maszter