13-7 判断子树的形状的代码不是很理解

Question

老师你好！ 第12分钟 ，判断树形状的那三个if，后面两个条件我都理解了 ，可是第一个情况，对Node的左子树进行左旋转的那个不是很理解，当前的Node不是黑色的那个节点吗，可是代码里面的判断是以Node的为基准进行操作的呀？

Answer 1

liuyubobobo 2019-04-29 10:18:31

不知道我是不是没有理解你的问题。第一个if左旋转对应ppt讲的这种情况：

此时，当递归回溯到37节点的时候，满足第一个if，即37的右孩子是42，同时37的左孩子不能为红，就左旋转。（如果是红，37的左右孩子都是红色，做flip color就好了。）

此时，你可以再回顾一下左旋转，理解一下左旋转到底做了什么事情。是的，此时，要纠正42，需要从37的视角去做这个左旋转，旋转后，42是37的根，37变成了42的左孩子。请注意我们左旋转的注释：

//   node                     x    
//  /   \     左旋转         /  \    
// T1   x   --------->   node   T3    
//     / \              /   \    
//    T2 T3            T1   T2    
private Node leftRotate(Node node){    
  
    Node x = node.right;    
    
    // 左旋转    
    node.right = x.left;    
    x.left = node;    
    
    x.color = node.color;    
    node.color = RED;    
    
    return x;    
}

继续加油！：）

• 提问者 NioCo #1

  谢谢老师 ，我的疑问是这张图，第二个if判断的是第三步，第三个if判断的是第四步，可是第二小步中的if判断难道不是if(isRed(node.left) && isRed(node.left.right) ) 吗？
  
  --------------------------------------------
  我想我大概懂了 ，第一个if判断是递归回溯一次，第二个递归判断是回溯两次的，第三个也是回溯一次的情况，不知道是不是这样理解 ：）

Answer 2

提问者 NioCo 2019-04-29 12:30:06

谢谢老师 ，我的疑问是这张图，第二个if判断的是第三步，第三个if判断的是第四步，可是第二小步中的if判断难道不是if(isRed(node.left) && isRed(node.left.right) ) 吗？

• liuyubobobo #1

  对于第二小步，会先在第二个红色节点的位置执行左旋转。这发生在到达黑色节点，也就是你说的isRed(node.left) && isRed(node.left.right) 这个node之前：）

• 提问者 NioCo 回复 liuyubobobo #2

  原来是这样 ，谢谢老师！

• qq_Aquarius丶_0 回复 liuyubobobo #3

  懂了，我也正疑惑为什么这个左旋转对应的代码不对呢，谢谢老师！

点开查看后面1条评论