树的常见面试题

古城微笑少年丶 2024-04-08 09:49 80阅读 0赞

## 树的常见面试题 ##

### 1 树的后继节点 ###

> node的后继节点指的是中序遍历树之后，排在node后面一个节点

#### 1.1 题型一：求二插搜索树的后继节点（后继者） ####

> **题目链接:**https://leetcode.cn/problems/successor-lcci/

![在这里插入图片描述][9de784f0c9d846cbaf94f379811d10bd.png]  
思路：

> 利用二叉搜索树特性：根节点的值大于左子树，根节点的值小于右子树

首先，如果要寻找的p节点的右子树不为null  
①p.right != null  
直接找p右子树的最左节点，更新successor的值

if(p.right != null){
        
        //p的右子树不为null -> p的右子树的最左节点
        TreeNode node = p.right;
        while(node.left != null){
        
            node = node.left;
        }
        successor = node;
    }

②p.right == null  
通用代码：

TreeNode node = root;
    while(node != null){
        
    	if(p.val < node.val){
        
    		successor = node;
    		node = node.left;
    	}else{
        
    		//如果p节点在root的先左后右或先右后左，会返回null
    		//如果在一直左或一直右，返回其parent
    		node = node.right;
    	} 
    }

> 详细分析：

p的右子树为null，判断p节点在root节点的左边还是右边  
1）如果p在root节点左边：  
一直向下找，找到p节点的父节点，  
如果是"左右"(root节点左子树的右子树，先左后右)：直接返回父节点的父节点  
如果是"左左":直接返回父节点

2）如果p在root节点的右边:  
如果是"右左"（root节点的右子树的左子树）：直接返回parent  
如果是"右右":直接返回null

TreeNode node = root;
    while(node != null){
        
    	if(p.val < node.val){
        
    		successor = node;
    		node = node.left;
    	}else {
        
    		node = node.right;
    	}
    }

全部代码：

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        
            TreeNode successor = null;
            if(p.right != null){
        
                //p的右子树不为null -> p的右子树的最左节点
                TreeNode node = p.right;
                while(node.left != null){
        
                    node = node.left;
                }
                successor = node;
            } 
            //p的右子树为null
            TreeNode node = root;
            while(node != null){
        
                if(p.val < node.val){
        
                    //node往左
                    successor = node;
                    node = node.left;
                } else {
        
                    //p的值大于node的值
                    node = node.right;
                }
            }
            return successor;
        }
    }

#### 1.2 题型二：node节点多一个属性parent【指向其父亲】 ####

Node结构：

public static class Node{
        
        private int value;
        private Node left;
        private Node right;
        private Node parent;
    
        public Node(int value){
        
            this.value = value;
        }
    }

分两种情况：一种node的right为null，一种node的right不为null  
思路：  
①node.right != null

> 找到node节点右子树的最左节点【中序：左中右】

//找到最左边节点
    public static Node getLeftMost(Node node){
        
        if(node == null){
        
            return node;
        }
        while(node.left != null){
        
            node = node.left;
        }
        return node;
    }

②node.right == null

> 判断node是parent的左子树还是右子树：  
> 如果是左子树，直接返回parent；  
> 如果是右子树，让parent往上找【如果node为root的最右节点，while循环之后会返回null】

Node parent = node.parent;
    while(parent != null && parent.right == node){
         //当前节点是其父亲节点的右孩子【null】
        node = parent;
        parent = node.parent;
    }
    //当前节点是其父亲的左孩子
    return parent;

全部代码：

public static class Node{
        
         private int value;
         private Node left;
         private Node right;
         private Node parent;
    
         public Node(int value){
        
             this.value = value;
         }
     }
    
     public static Node getSuccessorNode(Node node){
        
         if(node == null){
        
             return null;
         }
         if(node.right != null){
        
             //node节点的右子树不为null,找到右子树的最左边节点
             return getLeftMost(node.right);
         } else {
         //无右子树【node：1.左孩子  2.右孩子 】
             Node parent = node.parent;
             while(parent != null && parent.right == node){
         //当前节点是其父亲节点的右孩子【null】
                 node = parent;
                 parent = node.parent;
             }
             //当前节点是其父亲的左孩子
             return parent;
         }
     }
     //找到最左边节点
     public static Node getLeftMost(Node node){
        
         if(node == null){
        
             return node;
         }
         while(node.left != null){
        
             node = node.left;
         }
         return node;
     }

### 2 验证类题目 ###

#### 2.1 判断树是否为完全二叉树或满二叉树 ####

##### 2.1.1 是否是完全二叉树 #####

> 完全二叉树是指除最后一层以外，其他层全满，且最后一层叶子节点排布必须是从左到右

先介绍解法二：【通过递归】  
思路：创建信息收集类，根据树的递归最后返回结果  
①信息收集类Info

②调用process方法返回结果

public static boolean isCBT2(Node head) {
        
        if (head == null) {
        
            return true;
        }
        return process(head).isCBT;
    }

③处理方法process的编写

//处理类
    public static Info process(Node node) {
        
        if (node == null) {
        
            //base case:跳出递归
            return new Info(true, true, 0);
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        //处理高度[+1：本层高度]
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        //判断是否是满二叉树：左右是否是满，左右高度是否相等
        boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
        //判断是否是完全二叉树：①左右树都为满     ②左子树为满 右子树为完全  ③左子树为完全 右子树为满
        boolean isCBT = false;
        if (isFull) {
        
            //为满二叉树的树一定是完全二叉树
            isCBT = true;
        } else {
        
            if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
        
                isCBT = true;
            }
            if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
        
                isCBT = true;
            }
            if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
        
                //左为满，右下面为null
                isCBT = true;
            }
        }
        return new Info(isCBT, isFull, height);
    }

解法二的全代码：

//创建信息收集类
    public static class Info {
        
        //是否是完全二叉树
        public boolean isCBT;
        //是否是满二叉树
        public boolean isFull;
        public int height;
    
        public Info(boolean isCBT, boolean isFull, int height) {
        
            this.isCBT = isCBT;
            this.isFull = isFull;
            this.height = height;
        }
    }
    
    public static boolean isCBT2(Node head) {
        
        if (head == null) {
        
            return true;
        }
        return process(head).isCBT;
    }
    
    //处理类
    public static Info process(Node node) {
        
        if (node == null) {
        
            //base case:跳出递归
            return new Info(true, true, 0);
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        //处理高度[+1：本层高度]
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        //判断是否是满二叉树：左右是否是满，左右高度是否相等
        boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
        //判断是否是完全二叉树：①左右树都为满     ②左子树为满 右子树为完全  ③左子树为完全 右子树为满
        boolean isCBT = false;
        if (isFull) {
        
            //为满二叉树的树一定是完全二叉树
            isCBT = true;
        } else {
        
            if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
        
                isCBT = true;
            }
            if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
        
                isCBT = true;
            }
            if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
        
                //左为满，右下面为null
                isCBT = true;
            }
        }

解法一：【通过队列依次来判断】

//使用队列
    public static boolean isCBT1(Node head) {
        
        if (head == null) {
        
            return true;
        }
        LinkedList<Node> queue = new LinkedList<>();
        //是否遇到过左右两个孩子不双全的节点[叶子节点]
        boolean leaf = false;
        Node l = null;
        Node r = null;
        queue.add(head);
        while (!queue.isEmpty()) {
        
            head = queue.poll();
            l = head.left;
            r = head.right;
            if (leaf && (r != null || l != null) || (l == null && r != null)) {
        
                //遇到了不双全的节点，发现当前节点不是叶节点
                return false;
            }
            if (l != null) {
        
                queue.add(l);
            }
            if (r != null) {
        
                queue.add(r);
            }
            if (l == null || r == null) {
        
                leaf = true;
            }
        }
        return true;
    }

最后，通过对数器验证解法二是否正确  
**全代码：**

import java.util.LinkedList;
    
    //判断是否是完全二叉树或满二叉树
    public class CBTOrFullDemo {
        
    
        //创建节点类
        public static class Node {
        
            private int value;
            private Node left;
            private Node right;
    
            public Node(int value) {
        
                this.value = value;
            }
        }
    
        //使用队列
        public static boolean isCBT1(Node head) {
        
            if (head == null) {
        
                return true;
            }
            LinkedList<Node> queue = new LinkedList<>();
            //是否遇到过左右两个孩子不双全的节点[叶子节点]
            boolean leaf = false;
            Node l = null;
            Node r = null;
            queue.add(head);
            while (!queue.isEmpty()) {
        
                head = queue.poll();
                l = head.left;
                r = head.right;
                if (leaf && (r != null || l != null) || (l == null && r != null)) {
        
                    //遇到了不双全的节点，发现当前节点不是叶节点
                    return false;
                }
                if (l != null) {
        
                    queue.add(l);
                }
                if (r != null) {
        
                    queue.add(r);
                }
                if (l == null || r == null) {
        
                    leaf = true;
                }
            }
            return true;
        }
    
        //创建信息收集类
        public static class Info {
        
            //是否是完全二叉树
            public boolean isCBT;
            //是否是满二叉树
            public boolean isFull;
            public int height;
    
            public Info(boolean isCBT, boolean isFull, int height) {
        
                this.isCBT = isCBT;
                this.isFull = isFull;
                this.height = height;
            }
        }
    
        public static boolean isCBT2(Node head) {
        
            if (head == null) {
        
                return true;
            }
            return process(head).isCBT;
        }
    
        //处理类
        public static Info process(Node node) {
        
            if (node == null) {
        
                //base case:跳出递归
                return new Info(true, true, 0);
            }
            Info leftInfo = process(node.left);
            Info rightInfo = process(node.right);
            //处理高度[+1：本层高度]
            int height = Math.max(leftInfo.height, rightInfo.height) + 1;
            //判断是否是满二叉树：左右是否是满，左右高度是否相等
            boolean isFull = leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height;
            //判断是否是完全二叉树：①左右树都为满     ②左子树为满 右子树为完全  ③左子树为完全 右子树为满
            boolean isCBT = false;
            if (isFull) {
        
                //为满二叉树的树一定是完全二叉树
                isCBT = true;
            } else {
        
                if (leftInfo.isFull && rightInfo.isCBT && leftInfo.height == rightInfo.height) {
        
                    isCBT = true;
                }
                if (leftInfo.isCBT && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
        
                    isCBT = true;
                }
                if (leftInfo.isFull && rightInfo.isFull && leftInfo.height == rightInfo.height + 1) {
        
                    //左为满，右下面为null
                    isCBT = true;
                }
            }
            return new Info(isCBT, isFull, height);
        }
    
        //定义对数器进行测试
        //for test
        public static Node generateTree(int maxLevel, int maxValue) {
        
            //从第1层开始
            return generate(1, maxLevel, maxValue);
        }
    
        //for test
        public static Node generate(int level, int maxLevel, int maxValue) {
        
            if (level > maxLevel || Math.random() < 0.5) {
        
                return null;
            }
            Node head = new Node((int) (Math.random() * maxValue));
            head.left = generate(level + 1, maxLevel, maxValue);
            head.right = generate(level + 1, maxLevel, maxValue);
            return head;
        }
    
        public static void main(String[] args) {
        
            int maxLevel = 6;
            int maxValue = 100;
            int times = 100_0000;
            for(int i = 0; i < times; i++){
        
                Node node = generateTree(maxLevel, maxValue);
                if(isCBT1(node) != isCBT2(node)){
        
                    System.out.println("Oops!");
                }
            }
            System.out.println("finish!");
        }
    }

##### 2.1.2 是否是满二叉树 #####

同上，同是否是完全二叉树一样，只需要返回isFull信息即可【递归方法】

[9de784f0c9d846cbaf94f379811d10bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/9740bdcd62e04019815b96fad3705c4d.png