【每日一练】谷歌面试题：用JAVA翻转二叉搜索树

系统管理员 2024-03-22 11:49 5阅读 0赞

#### 文章目录 ####

*   *  前言
     *  题目
     *  分析
     *  实战演示
     *   *  1、创建一颗搜索二叉树
         *  2、中序遍历二叉搜索树
         *  3、根据题意创建二叉搜索树并展示
         *  4、算法增加二叉树翻转方法
         *  5、根据题意测试翻转二叉树结果
         *  6、完整代码

### 前言 ###

很多同学应该都能够模拟出一个二叉树，那么又有多少同学能够写出翻转二叉树呢？有一道谷歌面试题：我们90％的工程师使用您编写的软件(Homebrew)，但是您却无法在面试时在白板上写出翻转二叉树这道题，这太糟糕了。  
![在这里插入图片描述][631085993a77475897ddfb09bd03ca87.png]

### 题目 ###

翻转一棵二叉树  
示例：  
输入：

4
       /   \
      2     7
     / \   / \
    1   3 6   9

输出：

4
       /   \
      7     2
     / \   / \
    9   6 3   1

### 分析 ###

1、根据示例翻转二叉树就是将所有的左右节点交换即可  
2、我们可以取到每一个节点，然后将左右节点交换，当然这是一个递归的操作  
3、为便于我们测试，我们采用二叉搜索树演示。  
4、二叉搜索树规则：左子节点必须小于父节点，右子节点必须大于父节点，所有左子节点最大值不大于当前父节点，所有右子节点最小值不小于当前父节点。

### 实战演示 ###

为方便测试我们需要先创建一个构建一颗二叉树的算法，然后再编写翻转二叉树的算法

#### 1、创建一颗搜索二叉树 ####

为了方便演示，我们仅实现添加节点的算法

/**
     * 创建二叉搜索树
     * 定义 左节点小于父节点，右节点大于父节点
     *
     */
    private void createTree(Node root,int val){
        
        if(Objects.isNull(root) || val == 0){
        
            return;
        }
        //封装节点
        Node node = new Node(val);
        //节点放入
        setNode(root,node);
    }
    
    
    
    /**
     * 设置节点
     * @param root
     * @param node
     * @author senfel
     * @date 2023/5/4 10:03
     * @return void
     */
    private void setNode(Node root, Node node) {
        
       if(node.val > root.val){
        
           //右节点
           if(root.rightNode == null){
        
               root.rightNode = node;
           }else{
        
               setNode(root.rightNode,node);
           }
       }else if(node.val < root.val){
        
           //左节点
           if(root.leftNode == null){
        
               root.leftNode = node;
           }else{
        
               setNode(root.leftNode,node);
           }
       }else{
        
           //相等不做处理
           return;
       }
    }
    
    /**
     * 节点
     */
    static class Node{
        
        /**
         * 值
         */
        int val;
        /**
         * 左节点
         */
        Node leftNode;
        /**
         * 右节点
         */
        Node rightNode;
    
        public Node(int val) {
        
            this.val = val;
        }
    }

#### 2、中序遍历二叉搜索树 ####

为了方便展示我们采用中序遍历二叉树

/**
     * 遍历打印二叉搜索树
     * 中序打印
     * @param node
     * @author senfel
     * @date 2023/5/4 10:28
     * @return void
     */
    public void toString(Node node){
        
        if(Objects.isNull(node)){
        
            return;
        }
        toString(node.leftNode);
        System.err.println("node-val:"+node.val);
        toString(node.rightNode);
    }

#### 3、根据题意创建二叉搜索树并展示 ####

**3.1 创建二叉搜索树测试用例**

public static void main(String[] args) {
        
        Node node = new Node(4);
        ReverseTreeDemo reverTreeDemo = new ReverseTreeDemo();
        reverTreeDemo.createTree(node,2);
        reverTreeDemo.createTree(node,7);
        reverTreeDemo.createTree(node,1);
        reverTreeDemo.createTree(node,3);
        reverTreeDemo.createTree(node,6);
        reverTreeDemo.createTree(node,9);
        System.err.println(node);
        reverTreeDemo.toString(node);
    }

**3.2 查看测试结果**

![在这里插入图片描述][18042c8d9f74410a8e27726ff6925abc.png]

**3.3 中序打印二叉树结果**

node-val:1
    node-val:2
    node-val:3
    node-val:4
    node-val:6
    node-val:7
    node-val:9
    
    
         4
       /   \
      2     7
     / \   / \
    1   3 6   9

#### 4、算法增加二叉树翻转方法 ####

/**
     * 翻转节点
     * 为了符合题意，相当于左右子树交换位置
     * @param root
     * @author senfel
     * @date 2023/5/4 10:37
     * @return void
     */
    private void reverseNode(Node root){
        
        if(Objects.isNull(root)){
        
            return;
        }
        Node rightNode = root.rightNode;
        root.rightNode = root.leftNode;
        root.leftNode = rightNode;
        if(root.leftNode != null){
        
            reverseNode(root.leftNode);
        }
        if(root.rightNode != null){
        
            reverseNode(root.rightNode);
        }
    }

#### 5、根据题意测试翻转二叉树结果 ####

**5.1 创建翻转测试用例**

**5.2 查看翻转结果**  
![在这里插入图片描述][2faaeff23d404ab3a1e455721d13be72.png]

**5.3 中序遍历二叉树翻转结果**

node-val:9
    node-val:7
    node-val:6
    node-val:4
    node-val:3
    node-val:2
    node-val:1
    
    
         4
       /   \
      7     2
     / \   / \
    9   6 3   1

#### 6、完整代码 ####

/**
     * 翻转二叉树demo
     * @author senfel
     * @version 1.0
     * @date 2023/5/4 9:38
     */
    public class ReverseTreeDemo {
        
    
        /**
         * 创建二叉搜索树
         * 定义 左节点小于父节点，右节点大于父节点
         *
         */
        private void createTree(Node root,int val){
        
            if(Objects.isNull(root) || val == 0){
        
                return;
            }
            //封装节点
            Node node = new Node(val);
            //节点放入
            setNode(root,node);
        }
    
    
    
        /**
         * 设置节点
         * @param root
         * @param node
         * @author senfel
         * @date 2023/5/4 10:03
         * @return void
         */
        private void setNode(Node root, Node node) {
        
           if(node.val > root.val){
        
               //右节点
               if(root.rightNode == null){
        
                   root.rightNode = node;
               }else{
        
                   setNode(root.rightNode,node);
               }
           }else if(node.val < root.val){
        
               //左节点
               if(root.leftNode == null){
        
                   root.leftNode = node;
               }else{
        
                   setNode(root.leftNode,node);
               }
           }else{
        
               //相等不做处理
               return;
           }
        }
    
        /**
         * 节点
         */
        static class Node{
        
            /**
             * 值
             */
            int val;
            /**
             * 左节点
             */
            Node leftNode;
            /**
             * 右节点
             */
            Node rightNode;
    
            public Node(int val) {
        
                this.val = val;
            }
        }
    
        /**
         * 翻转节点
         * 为了符合题意，相当于左右子树交换位置
         * @param root
         * @author senfel
         * @date 2023/5/4 10:37
         * @return void
         */
        private void reverseNode(Node root){
        
            if(Objects.isNull(root)){
        
                return;
            }
            Node rightNode = root.rightNode;
            root.rightNode = root.leftNode;
            root.leftNode = rightNode;
            if(root.leftNode != null){
        
                reverseNode(root.leftNode);
            }
            if(root.rightNode != null){
        
                reverseNode(root.rightNode);
            }
        }
    
    
        /**
         * 遍历打印二叉搜索树
         * 中序打印
         * @param node
         * @author senfel
         * @date 2023/5/4 10:28
         * @return void
         */
        public void toString(Node node){
        
            if(Objects.isNull(node)){
        
                return;
            }
            toString(node.leftNode);
            System.err.println("node-val:"+node.val);
            toString(node.rightNode);
        }
    
    
        /**
         * 测试用例
         * @param args
         */
        public static void main(String[] args) {
        
            Node node = new Node(4);
            ReverseTreeDemo reverTreeDemo = new ReverseTreeDemo();
            reverTreeDemo.createTree(node,2);
            reverTreeDemo.createTree(node,7);
            reverTreeDemo.createTree(node,1);
            reverTreeDemo.createTree(node,3);
            reverTreeDemo.createTree(node,6);
            reverTreeDemo.createTree(node,9);
            System.err.println(node);
            reverTreeDemo.toString(node);
            //翻转树的左右节点
            reverTreeDemo.reverseNode(node);
            System.err.println(node);
            reverTreeDemo.toString(node);
        }
    
    }

[631085993a77475897ddfb09bd03ca87.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/af99a1ec96044c50977df9aaa7a24538.png
[18042c8d9f74410a8e27726ff6925abc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/61e8e758c2e24659a17560d3d22e02c3.png
[2faaeff23d404ab3a1e455721d13be72.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/a2775d5383234024a8f2bac3f6f281e4.png