二叉树的部分练习题目

傷城~ 2022-11-14 14:56 126阅读 0赞

### 目录 ###

*  相同的树
 *  另一个树的子树
 *  二叉树的最大深度
 *  平衡二叉树
 *  对称二叉树
 *  二叉树的最近公共祖先
 *  二叉树创建字符串

# 相同的树 #

链接： [相同的树][Link 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]  
思路：先判断根节点是否相同，如果不同则false，然后在判断左子树和右子树

class Solution { 
        public boolean isSameTree(TreeNode p, TreeNode q) { 
            if (p == null && q == null) { 
                return true;
            }
            if (p == null || q == null) { 
                return false;
            }
            if (p.val!=q.val){ 
                return false;
            }
    
            if (!isSameTree(p.left, q.left)) { 
                return false;
            }
            return isSameTree(p.right, q.right);
        }
    }

# 另一个树的子树 #

链接：[另一个树的子树][Link 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]  
思路：从根节点判断是否相同的树，然后依次左子树，右子树

class Solution { 
        public boolean isSubtree(TreeNode s, TreeNode t) { 
            if(s==null){ 
                return false;
            }
            if (isSameTree(s, t)) { 
                return true;
            }
            if (isSubtree(s.left, t)) { 
                return true;
            }
            return isSubtree(s.right, t);
        }
    
        public boolean isSameTree(TreeNode p, TreeNode q) { 
            if (p == null && q == null) { 
                return true;
            }
            if (p == null || q == null) { 
                return false;
            }
            return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }

# 二叉树的最大深度 #

链接：[添加链接描述][Link 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]  
思路：也就是求二叉树 的高度，找左子树和右子树，然后返回高度较高的，然后加上根节点。

class Solution { 
        public int maxDepth(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
    
            return Integer.max(left, right) + 1;
        }
    }

# 平衡二叉树 #

链接：[平衡二叉树][Link 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]  
思路：获取二叉树每个结点的左子树高度和右子树高度，判断差值的绝对值是否满足要求

class Solution { 
        public boolean isBalanced(TreeNode root) { 
            if (root == null) { 
                return true;
            }
            int left = getHeight(root.left);
            int right = getHeight(root.right);
            int diff = Math.abs(left - right);
            if (diff > 1) { 
                return false;
            }
            if (!isBalanced(root.left)) { 
                return false;
            }
            return isBalanced(root.right);
    
        }
    
        private int getHeight(TreeNode root) { 
            if (root == null) { 
                return 0;
            }
            int left = getHeight(root.left);
            int right = getHeight(root.right);
            return Integer.max(left, right) + 1;
        }
    }

# 对称二叉树 #

链接： [对称二叉树][Link 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 4]  
思路：判断左子树的左孩子和右孩子 是否和 右子树的右孩子左孩子相等，这样就能判断是否对称。

class Solution { 
        public boolean isSymmetric(TreeNode root) { 
            if (root == null) { 
                return true;
            }
            return isSame(root.left, root.right);
        }
    
        public boolean isSame(TreeNode p, TreeNode q) { 
            if (p == null && q == null) { 
                return true;
            }
            if (p == null || q == null) { 
                return false;
            }
            if (p.val != q.val) { 
                return false;
            }
            if (!isSame(p.left, q.right)) { 
                return false;
            }
            return isSame(p.right, q.left);
        }
    }

# 二叉树的最近公共祖先 #

链接： [二叉树的最近公共祖先][Link 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 5]  
思路：判断两个节点的位置，如果一左一右，那么就是根节点，如果在同一个子树下，然后递归继续寻找。

class Solution { 
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { 
            if (root == p || root == q) { 
                return root;
            }
            boolean pindex = contains(root.left, p);
            boolean qindex = contains(root.left, q);
            if (pindex && !qindex) { 
                //p在左子树，q不在
                return root;
            }
            if (qindex && !pindex) { 
                //q在左子树，p不在
                return root;
            }
            if (pindex) { 
                //p、q在左子树，
                return lowestCommonAncestor(root.left, p, q);
            } else { 
                return lowestCommonAncestor(root.right, p, q);
            }
        }
    
        public boolean contains(TreeNode root, TreeNode node) { 
            if (root == null) { 
                return false;
            }
            if (root == node) { 
                return true;
            }
            if (contains(root.left, node)) { 
                return true;
            }
            return contains(root.right, node);
        }
    }

# 二叉树创建字符串 #

链接： [二叉树创建字符串][Link 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 6]

class Solution { 
        public String tree2str(TreeNode t) { 
            StringBuilder sb = new StringBuilder();
            doTree2str(t, sb);
            return sb.toString();
        }
        
        private void doTree2str(TreeNode t, StringBuilder sb) { 
            if (t != null) { 
                sb.append(t.val);
                if (t.left != null || t.right != null) { 
                    sb.append('(');
                    doTree2str(t.left, sb);
                    sb.append(')');
                    if (t.right != null) { 
                        sb.append('(');
                        doTree2str(t.right, sb);
                        sb.append(')');
                    }
                }
            }
        }
    }

[Link 1]: https://leetcode-cn.com/problems/same-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70]: /images/20221022/caa09a09fa5c45598c8c965f5541c556.png
[Link 2]: https://leetcode-cn.com/problems/subtree-of-another-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 1]: /images/20221022/9bc257d50e8b49ebbfff05c0d58795a7.png
[Link 3]: https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 2]: /images/20221022/3b7ee0844a2d411a8f202afc30526162.png
[Link 4]: https://leetcode-cn.com/problems/balanced-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 3]: /images/20221022/ed474c19fcd8421bae51a7c599168eed.png
[Link 5]: https://leetcode-cn.com/problems/symmetric-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 4]: /images/20221022/4ace100e5b844f398e5269d53c94ba7e.png
[Link 6]: https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 5]: /images/20221022/0fc8dc16c803460f8d000e5ddefeba46.png
[Link 7]: https://leetcode-cn.com/problems/construct-string-from-binary-tree/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MjE0MjczMQ_size_16_color_FFFFFF_t_70 6]: /images/20221022/7a875612a4734b48ab85c124da1e3185.png