剑指offer题解——树(二)

阳光穿透心脏的1/2处 2023-03-03 11:28 7阅读 0赞

### 文章目录 ###

*   *  剑指 Offer 34. 二叉树中和为某一值的路径
     *   *  解法
     *  剑指 Offer 37. 序列化二叉树
     *   *  解法
     *  剑指 Offer 54. 二叉搜索树的第k大节点
     *   *  递归
     *  剑指 Offer 55 - I. 二叉树的深度
     *   *  迭代解法
         *  递归解法
     *  剑指 Offer 55 - II. 平衡二叉树
     *   *  递归解法
     *  剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
     *   *  递归
     *  剑指 Offer 68 - II. 二叉树的最近公共祖先
     *   *  递归
         *   *  推荐阅读

## 剑指 Offer 34. 二叉树中和为某一值的路径 ##

[剑指 Offer 34. 二叉树中和为某一值的路径][Offer 34.]

输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。

示例:
    给定如下二叉树，以及目标和 sum = 22，
    
                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \    / \
            7    2  5   1
    返回:
    
    [
       [5,4,11,2],
       [5,8,4,5]
    ]
     
    
    提示：
    
    节点总数 <= 10000

### 解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        List<List<Integer>> res = new LinkedList<>();
        private void DFS(TreeNode root, Deque<Integer> stack, int sum) {
        
            if (root == null) {
        
                return;
            }
            stack.offerLast(root.val);
            if (root.val == sum && root.left == null && root.right == null) {
        
                res.add(new LinkedList<>(stack));
                stack.pollLast();
                return;
            }
            if (root.left != null) {
        
                DFS(root.left, stack, sum - root.val);
            }
            if (root.right != null) {
        
                DFS(root.right, stack, sum - root.val);
            }
            stack.pollLast();
        }
        public List<List<Integer>> pathSum(TreeNode root, int sum) {
        
            Deque<Integer> stack = new LinkedList<>();
            DFS(root, stack, sum);
            return res;
        }
    }

## 剑指 Offer 37. 序列化二叉树 ##

[剑指 Offer 37. 序列化二叉树][Offer 37.]

请实现两个函数，分别用来序列化和反序列化二叉树。

示例: 
    
    你可以将以下二叉树：
    
        1
       / \
      2   3
         / \
        4   5
    
    序列化为 "[1,2,3,null,null,4,5]"

### 解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    public class Codec {
        
        private StringBuilder serialize(TreeNode root, StringBuilder sb) {
        
            if (root == null) {
        
                sb.append("None,");
            } else {
        
                sb.append(String.valueOf(root.val) + ",");
                sb = serialize(root.left, sb);
                sb = serialize(root.right, sb);
            }
            return sb;
        }
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
        
            return serialize(root, new StringBuilder()).toString();
        }
        
        private TreeNode deserialize(List<String> list) {
        
            if (list.get(0).equals("None")) {
        
                list.remove(0);
                return null;
            }
            TreeNode root = new TreeNode(Integer.valueOf(list.get(0)));
            list.remove(0);
            root.left = deserialize(list);
            root.right = deserialize(list);
            return root;
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
        
            String[] dataArray = data.split(",");
            List<String> list = new LinkedList<String>(Arrays.asList(dataArray));
            return deserialize(list);
        }
    }
    
    // Your Codec object will be instantiated and called as such:
    // Codec codec = new Codec();
    // codec.deserialize(codec.serialize(root));

## 剑指 Offer 54. 二叉搜索树的第k大节点 ##

[剑指 Offer 54. 二叉搜索树的第k大节点][Offer 54. _k]

给定一棵二叉搜索树，请找出其中第k大的节点。

示例 1:
    
    输入: root = [3,1,4,null,2], k = 1
       3
      / \
     1   4
      \
       2
    输出: 4
    示例 2:
    
    输入: root = [5,3,6,2,4,null,null,1], k = 3
           5
          / \
         3   6
        / \
       2   4
      /
     1
    输出: 4
     
    
    限制：
    
    1 ≤ k ≤ 二叉搜索树元素个数

### 递归 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        int k, res;
        public int kthLargest(TreeNode root, int k) {
        
            this.k = k;
            dfs(root);
            return res;
        }
        private void dfs(TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            dfs(root.right);
            if (k == 0) {
        
                return;
            }
            if (--k == 0) {
        
                res = root.val;
            }
            dfs(root.left);
        }
    }

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

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

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

例如：
    
    给定二叉树 [3,9,20,null,null,15,7]，
    
        3
       / \
      9  20
        /  \
       15   7
    返回它的最大深度 3 。
    
     
    
    提示：
    
    节点总数 <= 10000

### 迭代解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public int maxDepth(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            Deque<Pair<TreeNode, Integer>> stack = new LinkedList<>();
            if (root != null) {
        
                stack.addFirst(new Pair(root, 1));
            }
            int depth = 0;
            while(!stack.isEmpty()) {
        
                Pair<TreeNode, Integer> current = stack.removeFirst();
                root = current.getKey();
                int currentDepth = current.getValue();
                if (root != null) {
        
                    depth = Math.max(depth, currentDepth);
                    stack.addFirst(new Pair(root.left, currentDepth + 1));
                    stack.addFirst(new Pair(root.right, currentDepth + 1));
                }
            }
            return depth;
        }
    }

### 递归解法 ###

## 剑指 Offer 55 - II. 平衡二叉树 ##

[剑指 Offer 55 - II. 平衡二叉树][Offer 55 - II.]

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1:
    
    给定二叉树 [3,9,20,null,null,15,7]
    
        3
       / \
      9  20
        /  \
       15   7
    返回 true 。
    
    示例 2:
    
    给定二叉树 [1,2,2,3,3,null,null,4,4]
    
           1
          / \
         2   2
        / \
       3   3
      / \
     4   4
    返回 false 。
    
     
    
    限制：
    
    1 <= 树的结点个数 <= 10000

### 递归解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        private boolean flag = true;
        public boolean isBalanced(TreeNode root) {
        
            maxDepth(root);
            return flag;
        }
        private int maxDepth(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            if (Math.abs(leftDepth - rightDepth) > 1) {
        
                flag = false;
            }
            return 1 + Math.max(leftDepth, rightDepth);
        }
    }

## 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 ##

[剑指 Offer 68 - I. 二叉搜索树的最近公共祖先][Offer 68 - I.]

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = \[6,2,8,0,4,7,9,null,null,3,5\]

![format_png][]

示例 1:
    
    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    输出: 6 
    解释: 节点 2 和节点 8 的最近公共祖先是 6。
    示例 2:
    
    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
    输出: 2
    解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
     
    
    说明:
    
    所有节点的值都是唯一的。
    p、q 为不同节点且均存在于给定的二叉搜索树中。

### 递归 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            int val = root.val;
            if (val < p.val && val < q.val) {
        
                return lowestCommonAncestor(root.right, p, q);
            }
            if (val > p.val && val > q.val) {
        
                return lowestCommonAncestor(root.left, p, q);
            }
            return root;
        }
    }

## 剑指 Offer 68 - II. 二叉树的最近公共祖先 ##

[剑指 Offer 68 - II. 二叉树的最近公共祖先][Offer 68 - II.]

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

例如，给定如下二叉树: root = \[3,5,1,6,2,0,8,null,null,7,4\]  
![format_png 1][]

示例 1:
    
    输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
    输出: 3
    解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
    示例 2:
    
    输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
    输出: 5
    解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
     
    
    说明:
    
    所有节点的值都是唯一的。
    p、q 为不同节点且均存在于给定的二叉树中。

### 递归 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
            if (root == null || root == p || root == q) {
        
                return root;
            }
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            return left == null ? right : right == null ? left : root;
        }
    }

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

#### 推荐阅读 ####

*  [机器学习资料汇总][Link 1]
 *  [吴恩达《机器学习》视频、作业、源码][Link 2]
 *  [106页《Python进阶》中文版正式发布][106_Python]
 *  [李航《统计学习方法》第二版完整课件][Link 3]
 *  [机器学习数学全书，1900页PDF下载][1900_PDF]

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

![format_png 2][]

[Offer 34.]: https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/
[Offer 37.]: https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/
[Offer 54. _k]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
[Offer 55 - I.]: https://leetcode-cn.com/problems/er-cha-shu-de-shen-du-lcof/
[Offer 55 - II.]: https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof/
[Offer 68 - I.]: https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[format_png]: /images/20230208/89adb5443d9340519cb0822359202c76.png
[Offer 68 - II.]: https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
[format_png 1]: /images/20230208/366a5b90cef04fc48bf309172c822d50.png
[Link 1]: https://mp.weixin.qq.com/s/3nOkk_Yt9D7Qp1WaWEjyZQ
[Link 2]: https://mp.weixin.qq.com/s/dErZNtBYbVA7ItPm7T_HIw
[106_Python]: https://mp.weixin.qq.com/s/_WEuuxj-QgihijjLz7NJ9g
[Link 3]: https://mp.weixin.qq.com/s/xah47OWuu8ahAUa1aFFo4Q
[1900_PDF]: https://mp.weixin.qq.com/s/9BuyhdwuHiHH3ksVUe44ZQ
[format_png 2]: /images/20230208/def621a9704f45bdb1386e6eb5069a2f.png