【剑指offer-Java版】27二叉搜索树与双向链表

拼搏现实的明天。 2022-08-21 09:40 150阅读 0赞

二叉排序树转双向链表：又是一个不是很懂的递归，原理很懂，代码很懂，自己写就需要写很久  
需要多画画图，多在脑子里面模拟一下递归过程，缺乏此类训练

这个递归练习也是理解Java值传递和引用传递机制的极好分析案例  
比如原解法中通过一个引用副本进行传递，但是在递归调用过程中会出现左子树丢失的情形，  
但是Java并没有什么可以将对象的引用的修改进行保存的方法，所以就设置了个成员变量-很好的解决了，但是感觉不优雅-也没有C的那么纯粹

比较基础的问题，居然忘了：  
为什么递归传递对象的引用的时候会造成这种左子树丢失的情形呢？  
因为使用该lastNode的目的就是始终让其指向当前序列的最后结点，但是这段代码的逻辑是在一次递归调用当中，左子树的和右子树使用的是同一个对象引用的不同副本  
因此在一次调用之后，对左子树的修改并没有通过lastNode传递给右子树，因此也就无法通过lastNode将序列连接起来

实际运行中，每次递归调用ConvertNode()的时候都新建了一个lastNode的副本，而此处对引用指向的对象没有进行修改，而是修改引用的指向。但是对于形参副本的修改  
是无法反映在实参上面的。因此为了实现类似于C中的指针的效果，将引用副本指向的修改保留下来，就声明了一个全局变量

public class _Q27<T> {
    
        private BinaryTreeNode<Integer> lastNode = null;
    
        public BinaryTreeNode<Integer> Convert(BinaryTreeNode<Integer> tree){
            if(tree == null) return null;
    
            //BinaryTreeNode<Integer> lastNode = null;
            ConvertNode(tree/*, lastNode*/);
    
            // 但是tree结点无论如何都是在链表中的，那么把指向它的引用移动到链表首部即可
            BinaryTreeNode<Integer> head = tree;
            while(head != null && head.leftChild != null){
                head = head.leftChild;
            }
    
            return head;
        }
    
        private void ConvertNode(BinaryTreeNode<Integer> tree/*, BinaryTreeNode<Integer> lastNode*/){
    
            if(tree == null) return;
    
            BinaryTreeNode<Integer> curNode = tree;
    
            // 递归转换左子树最后结点
            if(curNode.leftChild != null){
                ConvertNode(curNode.leftChild/*, lastNode*/);
            }
    
            // 修改前后驱指针
            curNode.leftChild = lastNode;
            if (lastNode != null) {
                lastNode.rightChild = curNode;
            }
            lastNode = curNode;
    
            // 递归转换右子树
            if(curNode.rightChild != null){
                ConvertNode(curNode.rightChild/*, lastNode*/);
            }
        }
        }

测试代码：

public class _Q27Test extends TestCase {
        
    
        _Q27<Integer> convert = new _Q27<Integer>();
    
        public void test(){
    
            BinaryTreeNode<Integer> root = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node1 = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node2 = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node3 = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node4 = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node5 = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node6 = new BinaryTreeNode<>();
    
            root.value = 10;
            node1.value = 6;
            node2.value = 14;
            node3.value = 4;
            node4.value = 8;
            node5.value = 12;
            node6.value = 16;
    
            root.leftChild = node1;
            root.rightChild = node2;
            node1.leftChild = node3;
            node1.rightChild = node4;
            node2.leftChild = node5;
            node2.rightChild = node6;
    
            node3.leftChild = null; node3.rightChild = null;
            node4.leftChild = null; node4.rightChild = null;
            node5.leftChild = null; node5.rightChild = null;
            node6.leftChild = null; node6.rightChild = null;
    
            BinaryTreeNode<Integer> result = convert.Convert(root);
    
            while(result != null){
                System.out.print(result.value + " ");
                result = result.rightChild;
            }
        }
        }