二叉树：
种类：满二叉树、完全二叉树、二叉搜索树、平衡二叉搜索树
存储方式：链式存储、线式存储（顺序存储）
二叉数遍历：深度优先搜索（前序、中序、后序）：使用递归实现（实际用栈来实现）、迭代法（非递归的方式、栈），广度优先搜索（层序遍历）：用队列
递归三步走写法：1、确定递归函数的参数和返回值。2、确定终止条件。3、确定单层递归的逻辑。
144、二叉树的前序遍历
Leetcode刷题第五周

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 方法一：递归法
    // public List<Integer> preorderTraversal(TreeNode root) {
    //     List<Integer> result = new ArrayList<>();
    //     preorder(root, result);
    //     return result;
    // }
    // public void preorder(TreeNode root, List<Integer> result){
    //     if(root == null){
    //         return;
    //     }
    //     result.add(root.val);
    //     preorder(root.left, result);
    //     preorder(root.right, result);
    // }
    // 方法二：非递归的方法
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            if(cur != null){
                result.add(cur.val);
                stack.push(cur.right);
                stack.push(cur.left);
            }else{
                continue;
            }
        }
        return result;
    }
// 方法三：统一风格的非递归
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root != null){
            stack.push(root);
        }
        while(!stack.isEmpty()){
            if(stack.peek() != null){
                TreeNode cur = stack.pop();
                if(cur.right != null){
                    stack.push(cur.right);
                }
                if(cur.left != null){
                    stack.push(cur.left);
                }
                stack.push(cur);
                stack.push(null);
            }else{
                stack.pop();
                TreeNode cur = stack.pop();
                result.add(cur.val);
            }
        }
        return result;
    }
}

145、二叉树的后序遍历
Leetcode刷题第五周

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 方法一：递归法
    // public List<Integer> postorderTraversal(TreeNode root) {
    //     List<Integer> result = new ArrayList<>();
    //     postOrder(root, result);
    //     return result;
    // }
    // public void postOrder(TreeNode root, List<Integer> result){
    //     if(root == null){
    //         return;
    //     }
    //     postOrder(root.left, result);
    //     postOrder(root.right, result);
    //     result.add(root.val);
    // }
    // 方法二：非递归
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            result.add(cur.val);
            if(cur.left != null){
                stack.push(cur.left);
            }
            if(cur.right != null){
                stack.push(cur.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
// 方法三：统一风格的非递归
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root != null){
            stack.push(root);
        }
        while(!stack.isEmpty()){
            if(stack.peek() != null){
                TreeNode cur = stack.pop();
                stack.push(cur);
                stack.push(null);
                if(cur.right != null){
                    stack.push(cur.right);
                }
                if(cur.left != null){
                    stack.push(cur.left);
                }
            }else{
                stack.pop();
                TreeNode cur = stack.pop();
                result.add(cur.val);
            }
        }
        return result;
    }
}

94、二叉树的中序遍历
Leetcode刷题第五周

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 方法一：递归法
    // public List<Integer> inorderTraversal(TreeNode root) {
    //     List<Integer> result = new ArrayList<>();
    //     infixOrder(root, result);
    //     return result;
    // }
    // public void infixOrder(TreeNode root, List<Integer> result){
    //     if(root == null){
    //         return;
    //     }
    //     infixOrder(root.left, result);
    //     result.add(root.val);
    //     infixOrder(root.right, result);
    // }
    // 方法二：非递归
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.isEmpty()){
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }
        return result;
    }
// 方法三：统一风格的非递归
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if(root != null){
            stack.push(root);
        }
        while(!stack.isEmpty()){
            if(stack.peek() != null){
                TreeNode cur = stack.pop();
                if(cur.right != null){
                    stack.push(cur.right);
                }
                stack.push(cur);
                stack.push(null);
                if(cur.left != null){
                    stack.push(cur.left);
                }
            }else{
                stack.pop();
                TreeNode cur = stack.pop();
                result.add(cur.val);
            }
        }
        return result;
    }
}

广度优先搜索：层序遍历
102、二叉树的层序遍历
Leetcode刷题第五周

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        Queue<TreeNode> queue = new LinkedList<>();
        int size = 0;
        if(root != null){
            queue.offer(root);
            size = 1;
        }
        while(!queue.isEmpty()){
            List<Integer> list1 = new ArrayList<>();
            while(size > 0){
                TreeNode cur = queue.poll();
                list1.add(cur.val);
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
                size--;
            }
            size = queue.size();
            list.add(list1);
        }
        return list;
    }
}

107、二叉树的层序遍历 II
Leetcode刷题第五周

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        int size = queue.size();
        if(root != null){
            queue.offer(root);
            size = queue.size();
        }
        while(!queue.isEmpty()){
            List<Integer> list1 = new ArrayList<>();
            while(size > 0){
                TreeNode cur = queue.poll();
                list1.add(cur.val);
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
                size--;
            }
            size = queue.size();
            list.add(list1);
        }
        Collections.reverse(list);
        return list;
    }

199、二叉树的右视图
Leetcode刷题第五周

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> resultList = new ArrayList<>();
        Deque<TreeNode> deque = new LinkedList<>();
        int size = deque.size();
        if(root != null){
            deque.offer(root);
            size = deque.size();
        }
        while(!deque.isEmpty()){
            TreeNode cur = deque.peekLast();
            resultList.add(cur.val);
            while(size > 0){
                cur = deque.poll();
                if(cur.left != null){
                    deque.offer(cur.left);
                }
                if(cur.right != null){
                    deque.offer(cur.right);
                }
                size--;
            }
            size = deque.size();
        }
        return resultList;
    }
}

637、二叉树的层平均值
Leetcode刷题第五周

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> resultList =  new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        int size = queue.size();
        Double sum = 0.0;
        int count = 0;
        if(root != null){
            queue.offer(root);
            size = queue.size();
        }
        while(!queue.isEmpty()){
            count = size;
            while(size > 0){
                TreeNode cur = queue.poll();
                sum += cur.val;
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
                size--;
            }
            resultList.add(sum/count);
            sum = 0.0;
            size = queue.size();
        }
        return resultList;
    }
}

429、N 叉树的层序遍历
Leetcode刷题第五周

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> resultList = new ArrayList<>();
        Queue<Node> queue = new LinkedList<>();
        int size = queue.size();
        if(root != null){
            queue.offer(root);
            size = queue.size();
        }
        while(!queue.isEmpty()){
            List<Integer> list = new ArrayList<>();
            while(size > 0){
                Node cur = queue.poll();
                list.add(cur.val);
                for(Node node: cur.children){
                    if(node != null){
                        queue.offer(node);
                    }
                }
                size--;
            }
            resultList.add(list);
            size = queue.size();
        }
        return resultList;
    }
}

515、在每个树行中找最大值
Leetcode刷题第五周

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> resultList = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        int size = queue.size();
        if(root != null){
            queue.offer(root);
            size = queue.size();
        }
        int max = Integer.MIN_VALUE;
        while(!queue.isEmpty()){
            while(size > 0){
                TreeNode cur = queue.poll();
                max = max > cur.val ? max : cur.val;
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
                size--;
            }
            resultList.add(max);
            max = Integer.MIN_VALUE;
            size = queue.size();
        }
        return resultList;
    }
}

116
Leetcode刷题第五周

class Solution {
    public Node connect(Node root) {
        Queue<Node> queue = new LinkedList<>();
        int size = 0;
        if(root != null){
            queue.offer(root);
            size = queue.size();
        }
        while(!queue.isEmpty()){
            while(size > 0){
                Node temp = queue.poll();
                if(size > 1){
                    temp.next = queue.peek();
                }
                if(temp.left != null){
                    queue.offer(temp.left);
                }
                if(temp.right != null){
                    queue.offer(temp.right);
                }
                size--;
            }
            size = queue.size();
        }
        return root;
    }
}

117、填充每个节点的下一个右侧节点指针 II
Leetcode刷题第五周
同上！
104、二叉树的最大深度
![]
(https://cdn.yuucn.cn/wp-content/uploads/2022/12/1670158922-46aedc2cf171285.png)

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

111、二叉树的最小深度
Leetcode刷题第五周

class Solution {
    public int minDepth(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        int size = queue.size();
        int depth = 0;
        if(root != null){
            queue.offer(root);
            size = queue.size();
        }
        while(!queue.isEmpty()){
            depth++;
            while(size > 0){
                TreeNode cur = queue.poll();
                if(cur.left == null && cur.right == null){
                    return depth;
                }
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
                size--;
            }
            size = queue.size();
        }
        return depth;
    }
}

226、翻转二叉树
Leetcode刷题第五周

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 方法一：层次遍历，广度优先算法
    // public TreeNode invertTree(TreeNode root) {
    //     Queue<TreeNode> queue = new LinkedList<>();
    //     int size = queue.size();
    //     if(root != null){
    //         queue.offer(root);
    //         size = queue.size();
    //     }
    //     while(!queue.isEmpty()){
    //         while(size > 0){
    //             TreeNode cur = queue.poll();
    //             if(cur.left != null){
    //                 queue.offer(cur.left);
    //             }
    //             if(cur.right != null){
    //                 queue.offer(cur.right);
    //             }
    //             swapChildren(cur);
    //             size--;
    //         }
    //         size = queue.size();
    //     }
    //     return root;
    // }
    // public void swapChildren(TreeNode cur){
    //     TreeNode temp = cur.left;
    //     cur.left = cur.right;
    //     cur.right = temp;
    // }
    // 方法二：递归法，中序
    // public TreeNode invertTree(TreeNode root) {
    //     if(root == null){
    //         return root;
    //     }
    //     invertTree(root.left);
    //     invertTree(root.right);
    //     swapChildren(root);
    //     return root;
    // }     
    // public void swapChildren(TreeNode cur){
    //     TreeNode temp = cur.left;
    //     cur.left = cur.right;
    //     cur.right = temp;
    // }
    // 方法三：迭代法：中序，统一风格
    public TreeNode invertTree(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        if(root != null){
            stack.push(root);
        }
        while(!stack.isEmpty()){
            if(stack.peek() != null){
                TreeNode cur = stack.pop();
                if(cur.right != null)
                stack.push(cur.right);
                if(cur.left != null)
                stack.push(cur.left);
                stack.push(cur);
                stack.push(null);
                swapChildren(cur);
            }else{
                stack.pop();
                stack.pop();
            }
        }
        return root;
    }     
    public void swapChildren(TreeNode cur){
        TreeNode temp = cur.left;
        cur.left = cur.right;
        cur.right = temp;
    }
}

589、N 叉树的前序遍历
Leetcode刷题第五周

class Solution {
    // 方法一：递归
    // public List<Integer> resultList = new ArrayList<>();
    // public List<Integer> preorder(Node root) {
    //     if(root == null){
    //         return resultList;
    //     }
    //     resultList.add(root.val);
    //     for(Node node : root.children){
    //         preorder(node);
    //     }
    //     return resultList;
    // }
    // 方法二：迭代，统一风格
    public List<Integer> preorder(Node root) {
        List<Integer> resultList = new ArrayList<>();
        Stack<Node> stack = new Stack<>();
        if(root != null){
            stack.push(root);
        }
        while(!stack.isEmpty()){
            if(stack.peek() != null){
                Node cur = stack.pop();
                List<Node> list = new ArrayList<>();
                list = cur.children;
                for(int i = list.size() - 1; i >= 0; i--){
                    if(list.get(i) != null){
                        stack.push(list.get(i));
                    }
                }
                stack.push(cur);
                stack.push(null);
            }else{
                stack.pop();
                Node cur = stack.pop();
                resultList.add(cur.val);
            }
        }
        return resultList;
    }
}

590、N 叉树的后序遍历

101、对称二叉树
Leetcode刷题第五周

class Solution {
    // 方法一：递归，后序遍历
    // public boolean isSymmetric(TreeNode root) {
    //     return compare(root.left, root.right);
    // }
    // public boolean compare(TreeNode left, TreeNode right){
    //     if(left == null && right != null){
    //         return false;
    //     }
    //     if(right == null && left != null){
    //         return false;
    //     }
    //     if(right == null && left == null){
    //         return true;
    //     }
    //     if(left.val != right.val){
    //         return false;
    //     }
    //     boolean resultLeft = compare(left.left, right.right);
    //     boolean resultRight = compare(left.right, right.left);
    //     return resultLeft && resultRight;
    // }
    // 方法二：迭代
    public boolean isSymmetric(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offerFirst(root.left);
        deque.offerLast(root.right);
        while(!deque.isEmpty()){
            TreeNode left = deque.pollFirst();
            TreeNode right = deque.pollLast();
            if(left == null && right == null){
                continue;
            }
            if(left == null && right != null){
                return false;
            }
            if(left != null && right == null){
                return false;
            }
            if(left.val != right.val){
                return false;
            }
            deque.offerFirst(left.left);
            deque.offerFirst(left.right);
            deque.offerLast(right.right);
            deque.offerLast(right.left);
        }
        return true;
    }
}

559、N 叉树的最大深度
Leetcode刷题第五周

class Solution {
    public int maxDepth(Node root) {
        return preOrder(root);
    }
    public int preOrder(Node root){
        if(root == null){
            return 0;
        }
        int depth = 0;
        for(Node node : root.children){
            depth = Math.max(depth, preOrder(node));
        }
        return depth + 1;
    }
}

对称二叉树
二叉树的最大深度
二叉树的最小深度
完全二叉树的节点个数
平衡二叉树
二叉树的所有路径
404、左叶子之和
Leetcode刷题第五周

    public int sumOfLeftLeaves(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left = sumOfLeftLeaves(root.left);
        int right = sumOfLeftLeaves(root.right);
        int val = 0;
        if(root.left != null && root.left.left == null &&root.left.right == null){
            val = root.left.val;
        }
        int sum = left + right + val;
        return sum;
    }
}

513找树左下角的值
Leetcode刷题第五周

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        int size  = queue.size();
        if(root != null){
            queue.offer(root);
            size = queue.size();
        }
        int find = 0;
        while(!queue.isEmpty()){
            Queue<TreeNode> result = new LinkedList<>();
            while(size > 0){
                TreeNode cur = queue.poll();
                result.offer(cur);
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
                size--;
            }
            size = queue.size();
            find = result.peek().val;
        }
        return find;
    }
}

112、路径总和
Leetcode刷题第五周

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        List<Integer> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        pathSum(root, result, temp);
        return result.contains(targetSum);
    }
    public void pathSum(TreeNode root, List<Integer> result, List<Integer> temp){
        temp.add(root.val);
        if(root.left == null && root.right == null){
            int sum = 0;
            for(int i = 0; i < temp.size(); i++){
                sum += temp.get(i);
            }
            result.add(sum);
        }
        if(root.left != null){
            pathSum(root.left, result, temp);
            temp.remove(temp.size() - 1);
        }
        if(root.right != null){
            pathSum(root.right, result, temp);
            temp.remove(temp.size() - 1);
        }
    }
}

113、路径总和 II
Leetcode刷题第五周

class Solution {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        if(root == null){
            return result;
        }
        find(root, result, temp, targetSum);
        return result;
    }
    public void find(TreeNode root, List<List<Integer>> result, List<Integer> temp, int targetSum){
        temp.add(root.val);
        if(root.left == null && root.right == null){
            int sum = 0;
            for(int i = 0; i < temp.size(); i++){
                sum += temp.get(i);
            }
            if(sum == targetSum){
                result.add(new ArrayList<Integer>(temp));
            }
        }
        if(root.left != null){
            find(root.left, result, temp, targetSum);
            temp.remove(temp.size() - 1);
        }
        if(root.right != null){
            find(root.right, result, temp, targetSum);
            temp.remove(temp.size() - 1);
        }
    }
}

106、从中序与后序遍历序列构造二叉树
Leetcode刷题第五周

class Solution {
    public Map<Integer, Integer> map;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return find(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }
    public TreeNode find(int[] inorder, int inbegin, int inend, int[] postorder, int pobegin, int poend){
        if(inbegin >= inend || pobegin >= poend){
            return null;
        }
        int temp = map.get(postorder[poend - 1]);
        int len = temp - inbegin;
        TreeNode root = new TreeNode(inorder[temp]);
        root.left = find(inorder, inbegin, temp, postorder, pobegin, pobegin + len);
        root.right = find(inorder, temp + 1, inend, postorder, pobegin + len, poend - 1);
        return root;
    }
}

105、从前序与中序遍历序列构造二叉树
Leetcode刷题第五周

class Solution {
    public Map<Integer, Integer> map;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return find(inorder, 0, inorder.length, preorder, 0, preorder.length);
    }
    public TreeNode find(int[] inorder, int inbegin, int inend, int[] preorder, int prbegin, int prend){
        if(inbegin >= inend || prbegin >= prend){
            return null;
        }
        int temp = map.get(preorder[prbegin]);
        int len = temp - inbegin;
        TreeNode root = new TreeNode(inorder[temp]);
        root.left = find(inorder, inbegin, temp, preorder, prbegin + 1, prbegin + len + 1);
        root.right = find(inorder, temp + 1, inend, preorder, prbegin + len + 1, prend);
        return root;
    }
}

654、最大二叉树
Leetcode刷题第五周

class Solution {
    public Map<Integer, Integer> map;
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            map.put(nums[i], i);
        }
        return binaryTree(nums, 0, nums.length - 1);
    }
    public TreeNode binaryTree(int[] nums, int left, int right){
        int max = -1;
        for(int i = left; i <= right; i++){
            max = max > nums[i] ? max : nums[i];
        }
        if(max == -1){
            return null;
        }else{
            int index = map.get(max);
            TreeNode root = new TreeNode(max);
            root.left = binaryTree(nums, left, index - 1);
            root.right = binaryTree(nums, index + 1, right);
            return root;
        }
    }
}

617、合并二叉树
Leetcode刷题第五周

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode result = new TreeNode();
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 前序遍历，递归
        // if(root1 == null){
        //     return root2;
        // }
        // if(root2 == null){
        //     return root1;
        // }
        // root1.val += root2.val;
        // root1.left = mergeTrees(root1.left,root2.left);
        // root1.right = mergeTrees(root1.right,root2.right);
        // return root1;
        // 使用栈迭代
        // if(root1 == null){
        //     return root2;
        // }
        // if(root2 == null){
        //     return root1;
        // }
        // Stack<TreeNode> stack = new Stack<>();
        // stack.push(root1);
        // stack.push(root2);
        // while(!stack.isEmpty()){
        //     TreeNode cur2 = stack.pop();
        //     TreeNode cur1 = stack.pop();
        //     cur1.val += cur2.val;
        //     if(cur1.left != null && cur2.left != null){
        //         stack.push(cur1.left);
        //         stack.push(cur2.left);
        //     }else{
        //         if(cur1.left == null){
        //             cur1.left = cur2.left;
        //         }
        //     }
        //     if(cur1.right != null && cur2.right != null){
        //         stack.push(cur1.right);
        //         stack.push(cur2.right);
        //     }else{
        //         if(cur1.right == null){
        //             cur1.right = cur2.right;
        //         }
        //     }
        // }
        // return root1;
        // 使用队列迭代
        if(root1 == null){
            return root2;
        }
        if(root2 == null){
            return root1;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root1);
        queue.offer(root2);
        while(!queue.isEmpty()){
            TreeNode cur1 = queue.poll();
            TreeNode cur2 = queue.poll();
            cur1.val += cur2.val;
            if(cur1.left != null && cur2.left != null){
                queue.offer(cur1.left);
                queue.offer(cur2.left);
            }else{
                if(cur1.left == null){
                    cur1.left = cur2.left;
                }
            }
            if(cur1.right != null && cur2.right != null){
                queue.offer(cur1.right);
                queue.offer(cur2.right);
            }else{
                if(cur1.right == null){
                    cur1.right = cur2.right;
                }
            }
        }
        return root1;
    }
}

700、二叉搜索树中的搜索
Leetcode刷题第五周

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        // 递归
        // if(root == null){
        //     return null;
        // }
        // TreeNode result = new TreeNode();
        // if(root.val == val){
        //     result = root;
        // }else if(root.val < val){
        //     result = searchBST(root.right,val);
        // }else{
        //     result = searchBST(root.left,val);
        // }
        // return result;
        // 迭代
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            TreeNode cur = stack.pop();
            if(cur.val == val){
                return cur;
            }else if(cur.val < val){
                if(cur.right == null){
                    return null;
                }
                stack.push(cur.right);
            }else{
                if(cur.left == null){
                    return null;
                }
                stack.push(cur.left);
            }
        }
        return null;
    }
}

98、验证二叉搜索树
Leetcode刷题第五周

class Solution {
    public boolean isValidBST(TreeNode root) {
// 需要从底层往上传递判断结果，所以采用后序遍历
        if(root == null){
            return true;
        }
        return isValidBST1(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    public boolean isValidBST1(TreeNode root,long left, long right){
        if(root == null){
            return true;
        }
        if(root != null && (root.val <= left || root.val >= right)){
            return false;
        }
        boolean leftFlag = isValidBST1(root.left,left,root.val);
        boolean rightFlag = isValidBST1(root.right,root.val,right);
        if(leftFlag == false || rightFlag == false){
            return false;
        }
        return leftFlag && rightFlag;
    }
}
[530](https://cdn.yuucn.cn/wp-content/uploads/2022/12/1670158931-46aedc2cf171285.png)

class Solution {
public int result = Integer.MAX_VALUE;
TreeNode pre;
public int getMinimumDifference(TreeNode root) {
if(root == null){
return result;
}
traversal(root);
return result;
}
public void traversal(TreeNode cur){
if(cur == null){
return;
}
traversal(cur.left);
if(pre != null){
result = Math.min(result, cur.val - pre.val);
}
pre = cur;
traversal(cur.right);
}
}

[501](https://cdn.yuucn.cn/wp-content/uploads/2022/12/1670158931-46aedc2cf171285.png)

class Solution {
public int Maxcount;
public int count;
public List result;
public TreeNode pre;
public int[] findMode(TreeNode root) {
Maxcount = 0;
count = 0;
result = new ArrayList<>();
pre = null;
traversal(root);
int[] find = new int[result.size()];
for(int i = 0; i < result.size(); i++){
find[i] = result.get(i);
}
return find;
}
public void traversal(TreeNode root){
if(root == null){
return;
}
traversal(root.left);
if(pre == null || root.val != pre.val){
count = 1;
}else{
count++;
}
pre = root;
if(count > Maxcount){
result.clear();
result.add(root.val);
Maxcount = count;
}else if(count == Maxcount){
result.add(root.val);
}
traversal(root.right);
}
}

[236](https://cdn.yuucn.cn/wp-content/uploads/2022/12/1670158931-46aedc2cf171285.png)

class Solution {
public TreeNode result = null;
// public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// // 1、后序遍历，从下往上传递，从遇到p或q开始，往上传递true,当某个节点也叶子节点都为true时，找到最近工祖先
// // 递归
// postOrder(root,p.val,q.val);
// return result;
// }
// public boolean postOrder(TreeNode root, int p, int q){
// if(root == null){
// return false;
// }
// boolean leftFlag = postOrder(root.left,p,q);
// boolean rightFlag = postOrder(root.right,p,q);
// if(leftFlag && rightFlag){
// result = root;
// return true;
// }
// if((root.val == q || root.val == p) && (leftFlag || rightFlag)){
// result = root;
// return true;
// }
// if(root.val == q || root.val == p){
// return true;
// }
// if(leftFlag || rightFlag){
// return true;
// }
// return false;
// }
}

[235](https://cdn.yuucn.cn/wp-content/uploads/2022/12/1670158931-46aedc2cf171285.png)

class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
int left = Math.min(p.val,q.val);
int right = Math.max(p.val,q.val);
return infixTravesal(root,left,right);
}
public TreeNode infixTravesal(TreeNode root,int left,int right){
if(root == null){
return root;
}
if(root.val >= left && root.val <= right){
return root;
}
TreeNode tempLeft = infixTravesal(root.left,left,right);
TreeNode tempRight = infixTravesal(root.right,left,right);
if(tempLeft != null){
return tempLeft;
}else if(tempRight != null){
return tempRight;
}else{
return null;
}
}
}

[701](https://cdn.yuucn.cn/wp-content/uploads/2022/12/1670158931-46aedc2cf171285.png)

class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null){
return new TreeNode(val);
}
TreeNode result = root;
travesal(root,val);
return result;
}
public void travesal(TreeNode root, int val){
if(root == null){
return;
}
if(root.val < val){
if(root.right == null){
root.right = new TreeNode(val);
return;
}else{
travesal(root.right,val);
}
}else{
if(root.val > val && root.left == null){
root.left = new TreeNode(val);
return;
}else{
travesal(root.left,val);
}
}
}
}

[450](https://cdn.yuucn.cn/wp-content/uploads/2022/12/1670158931-46aedc2cf171285.png)

class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
root = delete(root,key);
return root;
}
public TreeNode delete(TreeNode root,int key){
if(root == null){
return null;
}
if(root.val < key){
root.right = delete(root.right,key);
}else if(root.val > key){
root.left = delete(root.left,key);
}else{
if(root.left == null)
return root.right;
if(root.right == null)
return root.left;
TreeNode cur = root.right;
TreeNode temp = root.right;
while(temp.left != null){
temp = temp.left;
}
temp.left = root.left;
return cur;
}
return root;

}

}

[669](https://cdn.yuucn.cn/wp-content/uploads/2022/12/1670158931-46aedc2cf171285.png)

class Solution {
public TreeNode trimBST(TreeNode root, int low, int high) {
if(root == null){
return null;
}
if(root.val < low){
return trimBST(root.right,low,high);
}
if(root.val > high){
return trimBST(root.left,low,high);
}
root.left = trimBST(root.left,low,high);
root.right = trimBST(root.right,low,high);
return root;
}
}

[108](https://cdn.yuucn.cn/wp-content/uploads/2022/12/1670158931-46aedc2cf171285.png)

class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return travesal(nums,0,nums.length - 1);
}
public TreeNode travesal(int[] nums, int left, int right){
if(left > right){
return null;
}
int mid = left + (right - left)/2;
TreeNode result = new TreeNode(nums[mid]);
result.left = travesal(nums,left,mid - 1);
result.right = travesal(nums,mid + 1, right);
return result;
}
}

[538](https://cdn.yuucn.cn/wp-content/uploads/2022/12/1670158931-46aedc2cf171285.png)

class Solution {
public int sum = 0;
public TreeNode convertBST(TreeNode root) {
if(root == null){
return null;
}
convertBST(root.right);
root.val += sum;
sum = root.val;
convertBST(root.left);

    return root;
}

}

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。