Day25——二叉树专题

浅浅的花香味﹌ 2024-04-01 13:43 36阅读 0赞

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

*   *   *   *  5.翻转二叉树
             *  6.对称二叉树
             *  7.二叉树最大的深度

--------------------

##### 5.翻转二叉树 #####

**递归三部曲：**

1.确定递归函数的参数和返回值：返回值的话其实也不需要，但是题目中给出的要返回root节点的指针，可以直接使用题目定义好的函数

2.确定终止条件：当前节点为空的时候，就返回

3.确定单层递归的逻辑：因为是先前序遍历，所以先进行交换左右孩子节点，然后反转左子树，反转右子树

**思路**：递归实现

*  如果根节点不为空，那么就要交换其左右子树（即使左右子树是空节点也没关系）
 *  递归交换左右子树

class Solution {
        
        public TreeNode invertTree(TreeNode root) {
        
            dfs(root);
            return root;
        }
        public static void dfs(TreeNode root){
        
            if(root==null){
        
                return;
            }
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
    
            dfs(root.left);
            dfs(root.right);
        }
    }

**思路二:**`BFS`

//BFS
    class Solution {
        
        public TreeNode invertTree(TreeNode root) {
        
            if (root == null) {
        return null;}
            ArrayDeque<TreeNode> deque = new ArrayDeque<>();
            deque.offer(root);
            while (!deque.isEmpty()) {
        
                int size = deque.size();
                while (size-- > 0) {
        
                    TreeNode node = deque.poll();
                    swap(node);
                    if (node.left != null) {
        deque.offer(node.left);}
                    if (node.right != null) {
        deque.offer(node.right);}
                }
            }
            return root;
        }
        public void swap(TreeNode root) {
        
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
        }
    }

##### 6.对称二叉树 #####

递归：同时遍历左右子树，**左右子树是否完全对称**

*  两个根节点的值要相等
 *  左边的左子树和右边的右子树对称
 *  左边的右子树和右边的左子树对称

class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            return compare(root.left,root.right);
        }
        private boolean compare(TreeNode left,TreeNode right){
        
            if(left==null&&right!=null){
        
                return false;
            }
            else if(left!=null&&right==null){
        
                return false;
            }
            else if(left==null&&right==null){
        
                return true;
            }
            else if(left.val!=right.val){
        
                return false;
            }
            boolean compareOutside = compare(left.left,right.right);
            boolean compareInside = compare(left.right,right.left);
            return compareInside&&compareOutside;
        }
    }

##### 7.二叉树最大的深度 #####

**思路**`：dfs`，前序遍历统计最大深度即可

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