初级算法之树

男娘i 2024-03-30 16:03 33阅读 0赞

树比链表稍微复杂，因为链表是线性数据结构，而树不是。 树的问题可以由 广度优先搜索 或 深度优先搜索 解决。 在本章节中，我们提供了一个对于练习 广度优先遍历 很好的题目。

我们推荐以下题目：

二叉树的最大深度，验证二叉搜索树，二叉树的层次遍历 和 将有序数组转换为二叉搜索树。

## [剑指 Offer 55 - I. 二叉树的深度][Offer 55 - I.] ##

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

### 递归法: ###

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

### 迭代法: ###

class Solution {
        public int maxDepth(TreeNode root) {
           if(root == null) return 0;
            Queue<TreeNode> queue = new LinkedList<>(){
       {
                add(root);
            }};
            int depth = 0;
            while(!queue.isEmpty()){
                int cursize = queue.size();
                for(int i = 0; i < cursize; i++){
                    TreeNode temp = queue.poll();
                    if(temp.left != null) queue.add(temp.left);
                    if(temp.right != null) queue.add(temp.right);
                }
                depth++;
            }
            return depth;
        }
    }

## [111. 二叉树的最小深度][111.] ##

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：** 叶子节点是指没有子节点的节点。

class Solution {
        public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // null节点不参与比较
        if (root.left == null && root.right != null) {
            return 1 + minDepth(root.right);
        }
        // null节点不参与比较
        if (root.right == null && root.left != null) {
            return 1 + minDepth(root.left);
        }
    
        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }

广度优先算法

class Solution {
        class QueueNode {
            TreeNode node;
            int depth;
    
            public QueueNode(TreeNode node, int depth) {
                this.node = node;
                this.depth = depth;
            }
        }
    
        public int minDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
    
            Queue<QueueNode> queue = new LinkedList<QueueNode>();
            queue.offer(new QueueNode(root, 1));
            while (!queue.isEmpty()) {
                QueueNode nodeDepth = queue.poll();
                TreeNode node = nodeDepth.node;
                int depth = nodeDepth.depth;
                if (node.left == null && node.right == null) {
                    return depth;
                }
                if (node.left != null) {
                    queue.offer(new QueueNode(node.left, depth + 1));
                }
                if (node.right != null) {
                    queue.offer(new QueueNode(node.right, depth + 1));
                }
            }
    
            return 0;
        }
    }

## [98. 验证二叉搜索树][98.] ##

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 小于 当前节点的数。

节点的右子树只包含 大于 当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

### 递归 ###

class Solution {
            public boolean isValidBST(TreeNode root) {
            if (root == null) return true;
            return dfs(root.left, root.val, false) && dfs(root.right, root.val, true) && isValidBST(root.left) && isValidBST(root.right);
        }
    
        public boolean dfs(TreeNode root, int val, boolean moreThan) {
            if (root == null) return true;
            if (moreThan && root.val <= val) return false;
            if (! moreThan && root.val >= val) return false;
            if (root.left != null && ! dfs(root.left, val, moreThan)) return false;
            if (root.right != null && ! dfs(root.right, val, moreThan)) return false;
            return true;
        }
    }

class Solution {
        public boolean isValidBST(TreeNode root) {
            return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
        }
    
        public boolean isValidBST(TreeNode node, long lower, long upper) {
            if (node == null) {
                return true;
            }
            if (node.val <= lower || node.val >= upper) {
                return false;
            }
            return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
        }
    }

## [1361. 验证二叉树][1361.] ##

二叉树上有 n 个节点，按从 0 到 n - 1 编号，其中节点 i 的两个子节点分别是 leftChild\[i\] 和 rightChild\[i\]。

只有 所有 节点能够形成且 只 形成 一颗 有效的二叉树时，返回 true；否则返回 false。

如果节点 i 没有左子节点，那么 leftChild\[i\] 就等于 -1。右子节点也符合该规则。

二叉树的充分条件：

1）根节点不能被访问到

2）其他节点都被访问到且只被访问一次

用一个长度为 n 的数组 cnt 来记录访问次数 做判断

public boolean validateBinaryTreeNodes(int n, int[] leftChild, int[] rightChild) {
            int[] cnt = new int[n];
            for(int i=0; i<n; i++) {
                if(leftChild[i] >= 0) {
                    cnt[leftChild[i]] += 1;
                }
                if(rightChild[i] >= 0) {
                    cnt[rightChild[i]] += 1;
                }
            }
            if(cnt[0] != 0) {
                return false;
            }
            for(int i=1; i<n; i++) {
                if(cnt[i] != 1) {
                    return false;
                }
            }
            return true;
        }

## [剑指 Offer 28. 对称的二叉树][Offer 28.] ##

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

### 递归法 ###

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

### 迭代法 ###

class Solution {
        public boolean isSymmetric(TreeNode root) {
            return check(root, root);
        }
    
        public boolean check(TreeNode u, TreeNode v) {
            Queue<TreeNode> q = new LinkedList<TreeNode>();
            q.offer(u);
            q.offer(v);
            while (!q.isEmpty()) {
                u = q.poll();
                v = q.poll();
                if (u == null && v == null) {
                    continue;
                }
                if ((u == null || v == null) || (u.val != v.val)) {
                    return false;
                }
    
                q.offer(u.left);
                q.offer(v.right);
    
                q.offer(u.right);
                q.offer(v.left);
            }
            return true;
        }
    }

## [102. 二叉树的层序遍历][102.] ##

给你二叉树的根节点 root ，返回其节点值的 **层序遍历** 。 （即逐层地，从左到右访问所有节点）。

//dnf方法
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        levelHelper(res, root, 0);
        return res;
        }
        public void levelHelper(List<List<Integer>> list, TreeNode root, int level) {
        //边界条件判断
        if (root == null)
            return;
        //level表示的是层数，如果level >= list.size()，说明到下一层了，所以
        //要先把下一层的list初始化，防止下面add的时候出现空指针异常
        if (level >= list.size()) {
            list.add(new ArrayList<>());
        }
        //level表示的是第几层，这里访问到第几层，我们就把数据加入到第几层
        list.get(level).add(root.val);
        //当前节点访问完之后，再使用递归的方式分别访问当前节点的左右子节点
        levelHelper(list, root.left, level + 1);
        levelHelper(list, root.right, level + 1);
        }
    }

class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> ret = new ArrayList<List<Integer>>();
            if (root == null) {
                return ret;
            }
    
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                List<Integer> level = new ArrayList<Integer>();
                int currentLevelSize = queue.size();
                for (int i = 1; i <= currentLevelSize; ++i) {
                    TreeNode node = queue.poll();
                    level.add(node.val);
                    if (node.left != null) {
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        queue.offer(node.right);
                    }
                }
                ret.add(level);
            }
            
            return ret;
        }
    }

## [109. 有序链表转换二叉搜索树][109.] ##

给定一个单链表的头节点 head ，其中的元素 按升序排序 ，将其转换为高度平衡的二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差不超过 1。

class Solution {
        public TreeNode sortedListToBST(ListNode head) {
            if(head == null) return null;
            else if(head.next == null) return new TreeNode(head.val);
            ListNode pre = head;
            ListNode p = pre.next;
            ListNode q = p.next;
            //找到链表的中点p
            while(q!=null && q.next!=null){
                pre = pre.next;
                p = pre.next;
                q = q.next.next;
            }
            //将中点左边的链表分开
            pre.next = null;
            TreeNode root = new TreeNode(p.val);
            root.left = sortedListToBST(head);
            root.right = sortedListToBST(p.next);
            return root;
        }
    }

class Solution {
        public TreeNode sortedListToBST(ListNode head) {
            // 快慢指针找到链表的中点，中点作为根结点，两边作为左右子树
            if(head == null) return null;
            if(head.next == null) return new TreeNode(head.val);
            // 快慢指针找中间结点
            ListNode fast = head, slow = head, pre = null;
            while(fast != null && fast.next != null){
                fast =  fast.next.next;
                pre = slow;
                slow = slow.next;
            }
            // 分割出左链表，用于构造本结点的左子树
            pre.next = null;
            // 分割出右链表，用于构造本结点的右子树
            ListNode rightList = slow.next;
            // 用中间结点构造根结点
            TreeNode root = new TreeNode(slow.val);
            // 构造左子树
            root.left = sortedListToBST(head);
            // 构造右子树
            root.right = sortedListToBST(rightList);
            // 返回本结点所在子树
            return root;
        }
    }

## [108. 将有序数组转换为二叉搜索树][108.] ##

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

class Solution {
        public TreeNode sortedArrayToBST(int[] nums) {
            return nums == null ? null : buildTree(nums, 0, nums.length - 1);
        }
    
    
        private TreeNode buildTree(int[] nums, int l, int r) {
            if (l > r) {
                return null;
            }
            int m = l + (r - l) / 2;
            //根节点
            TreeNode root = new TreeNode(nums[m]);
            //左节点
            root.left = buildTree(nums, l, m - 1);
            //右节点
            root.right = buildTree(nums, m + 1, r);
            return root;
        }
    }

[Offer 55 - I.]: https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/
[111.]: https://leetcode.cn/problems/minimum-depth-of-binary-tree/
[98.]: https://leetcode.cn/problems/validate-binary-search-tree/
[1361.]: https://leetcode.cn/problems/validate-binary-tree-nodes/
[Offer 28.]: https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/
[102.]: https://leetcode.cn/problems/binary-tree-level-order-traversal/
[109.]: https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/
[108.]: https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/