我正在尝试解决这个问题"二叉树颠倒"。例如,如果我们有一个二叉树:
1
/
2 3
/
4 5
运行我的函数后,它将变成:
4
/
5 2
/
3 1
我得到了以下递归代码,但无法理解//1 和//5 之间的步骤;
public TreeNode UpsideDownBinaryTree(TreeNode root)
{
if (root == null) return null;
TreeNode parent = root, left = root.left, right = root.right;
if (left != null)
{
TreeNode ret = UpsideDownBinaryTree(left); //1
left.left = right; //2
left.right = parent; //3
return ret; //4
}
return root; //5
}
有人可以详细向我解释这里的每一步都在做什么吗?另外,为什么我们有两个单独的回报:return ret
、return root
?
我知道如何对常规数组、列表和一些二叉树进行递归。但是这种递归逻辑似乎与我以前所知道的有所不同。我什至使用IDE逐步完成,但仍然无法完全理解它。
我也有以下迭代代码来回答这个问题。我可以理解这段代码。它从根到叶扫描树。但是对于递归代码,它是从根到离开扫描树并从离开到根构建新树?我理解正确吗?
public TreeNode UpSideDownTree_Iterative(TreeNode root)
{
TreeNode node = root,parent = null,right = null;
while (node != null) {
TreeNode left = node.left;
node.left = right;
right = node.right;
node.right = parent;
parent = node;
node = left;
}
return parent;
}
从上次调用向后查看它可能会有所帮助。
该方法使用左节点递归调用,因此将使用节点 1、2 和 4 调用。
左最后一个节点(叶(是节点 4:查看评论:
//when invoked with node 4
public TreeNode UpsideDownBinaryTree(TreeNode root)
{
if (root == null) return null;
TreeNode parent = root; //node 4
TreeNode leftNode = root.left; //null
TreeNode rightNode = root.right; //null
if (leftNode != null)
{
//not executed
TreeNode ret = UpsideDownBinaryTree(leftNode); //invoke with 2
leftNode.left = rightNode; //left of node 2 becomes node 3
leftNode.right = parent; //right of node 2 becomes 1
return ret;
}
return root; //returned. The leaf becomes new root
}
让我们看看上一步:它返回到上一个调用(节点 2(:
//when invoked with node 2
public TreeNode UpsideDownBinaryTree(TreeNode root)
{
if (root == null) return null;
TreeNode parent = root; //node 2
TreeNode leftNode = root.left; //node 4
TreeNode rightNode = root.right; //node 5
if (leftNode != null)
{
TreeNode ret = UpsideDownBinaryTree(leftNode); //invoke with node 4
//as seen above return
//value is node 4
//which is the new root
leftNode.left = rightNode; //left of node 4 becomes node 5
leftNode.right = parent; //right of node 4 becomes 2
return ret; //node 4 returned, the new root
}
return root;
}
第一次调用(节点 1(与节点 2 非常相似。