使用递归的二叉搜索树遍历

Question

Q.我对使用递归和返回的二叉搜索树遍历有疑问。我必须拿一个按升序排列键的 BST，并"反转"它，以便所有键都按降序排列，如图所示。

根据我对以下代码的理解，我认为步骤是：

  ->reverseKeys (10)  ->reverseKeys (2)
  ->reverseKeys (null): return 
  ->reversekeys(null): return 
  ->BSTNODE <T> ptr = root.left; 
  ->root.left = root.right;
  ->root.right = ptr;  

我想我误解了代码。有人可以解释一下这段代码如何将左边的图片改到右边吗？我将不胜感激任何帮助。

   25                 25 
  /                 /   
 10  40      --->   40   10 
 /   /           /   /  
2 20 30 45        45 30 20  2 
 /                  /   
15    35            35   15 
 public static <T extends Comparable<T>> 
void reverseKeys(BSTNode<T> root) {
   if (root == null) { 
      return;
   }
   reverseKeys(root.left);
   reverseKeys(root.right);
   BSTNode<T> ptr = root.left;
   root.left = root.right;
   root.right = ptr;
}

Answer 1

这些行只是交换节点的左右子树。并且由于对方法的递归调用，每个节点在执行方法时都会交换左右子树。

BSTNode<T> ptr = root.left;
root.left = root.right;
root.right = ptr;

Answer 2

检查以下代码的 BST - 逆序遍历 (RVL(

public void traverse (Node root){ // Each child of a tree is a root of its subtree.
    if (root.left != null){
        traverse (root.left);
    }
    System.out.println(root.data);
    if (root.right != null){
        traverse (root.right);
    }
}
// Search with a valid node returned, assuming int
public Node traverse (Node root, int data){ // What data are you looking for again?
    if(root.data == data) {
        return root;
    }
    if (root.left != null){
        return traverse (root.left, data);
    }
    if (root.right != null){
        return traverse (root.right, data);
    }
    return null;
}