LeetCode题解——树(一)

清疚 2023-02-15 12:41 34阅读 0赞

### 文章目录 ###

*  递归
 *   *  二叉树的最大深度
     *   *  递归解法
         *  非递归解法
     *  平衡二叉树
     *   *  解法
     *  二叉树的直径
     *   *  解法
     *  翻转二叉树
     *   *  递归解法
     *  合并二叉树
     *   *  递归解法
     *  路径总和
     *   *  递归解法
     *  路径总和 III
     *   *  解法
     *  另一个树的子树
     *   *  递归解法
         *   *  推荐阅读

# 递归 #

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

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

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

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

示例：
    给定二叉树 [3,9,20,null,null,15,7]，
    
        3
       / \
      9  20
        /  \
       15   7
    返回它的最大深度 3 。

### 递归解法 ###

### 非递归解法 ###

/**
     * 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;
        }
    }

## 平衡二叉树 ##

给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过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 。

### 解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        private boolean result = true;
        public boolean isBalanced(TreeNode root) {
        
            maxDepth(root);
            return result;
        }
        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) {
        
                result = false;
            }
            return 1 + Math.max(leftDepth, rightDepth);
            
        }
    }

## 二叉树的直径 ##

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
    给定二叉树
    
              1
             / \
            2   3
           / \     
          4   5    
    返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

### 解法 ###

左子树高度加右子树高度的最大值

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        private int max = 0;
        public int diameterOfBinaryTree(TreeNode root) {
        
            depth(root);
            return max;
        }
        private int depth(TreeNode root) {
        
            if (root == null) {
        
                return 0;
            }
            int leftDepth = depth(root.left);
            int rightDepth = depth(root.right);
            max = Math.max(max, leftDepth + rightDepth);
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }

## 翻转二叉树 ##

翻转一棵二叉树。

示例：
    
    输入：
    
         4
       /   \
      2     7
     / \   / \
    1   3 6   9
    输出：
    
         4
       /   \
      7     2
     / \   / \
    9   6 3   1

### 递归解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode invertTree(TreeNode root) {
        
            if (root == null) {
        
                return null;
            }
            TreeNode temp = root.right;
            root.right = invertTree(root.left);
            root.left = invertTree(temp);
            return root;
        }
    }

## 合并二叉树 ##

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:
    
    输入: 
    	Tree 1                     Tree 2                  
              1                         2                             
             / \                       / \                            
            3   2                     1   3                        
           /                           \   \                      
          5                             4   7                  
    输出: 
    合并后的树:
    	     3
    	    / \
    	   4   5
    	  / \   \ 
    	 5   4   7
    注意: 合并必须从两个树的根节点开始。

### 递归解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        
            if (t1 == null && t2 == null) {
        
                return null;
            }
            if (t1 == null) {
        
                return t2;
            }
            if (t2 == null) {
        
                return t1;
            }
            TreeNode root = new TreeNode(t1.val + t2.val);
            root.left = mergeTrees(t1.left, t2.left);
            root.right = mergeTrees(t1.right, t2.right);
            return root;
        }
    }

## 路径总和 ##

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

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

示例: 
    给定如下二叉树，以及目标和 sum = 22，
    
                  5
                 / \
                4   8
               /   / \
              11  13  4
             /  \      \
            7    2      1
    返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

### 递归解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public boolean hasPathSum(TreeNode root, int sum) {
        
            if (root == null) {
        
                return false;
            }
            if (root.right == null && root.left == null && root.val == sum) {
        
                return true;
            }
            int tmp = sum - root.val;
            return hasPathSum(root.left, tmp) || hasPathSum(root.right, tmp);
        }
    }

## 路径总和 III ##

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 \[-1000000,1000000\] 的整数。

示例：
    
    root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8
    
          10
         /  \
        5   -3
       / \    \
      3   2   11
     / \   \
    3  -2   1
    
    返回 3。和等于 8 的路径有:
    
    1.  5 -> 3
    2.  5 -> 2 -> 1
    3.  -3 -> 11

### 解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public int pathSum(TreeNode root, int sum) {
        
            if (root == null) {
        
                return 0;
            }
            int ret = subPathSum(root, sum)+ pathSum(root.right, sum) + pathSum(root.left, sum);
            return ret;
        }
        public int subPathSum(TreeNode root, int sum) {
        
            if (root == null) {
        
                return 0;
            }
            int ret = 0;
            if (root.val == sum) {
        
                ret++;
            }
            ret += subPathSum(root.right, sum - root.val) + subPathSum(root.left, sum - root.val);
            return ret;
        }
    }

## 另一个树的子树 ##

给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

示例 1:
    给定的树 s:
    
         3
        / \
       4   5
      / \
     1   2
    给定的树 t：
    
       4 
      / \
     1   2
    返回 true，因为 t 与 s 的一个子树拥有相同的结构和节点值。
    
    示例 2:
    给定的树 s：
    
         3
        / \
       4   5
      / \
     1   2
        /
       0
    给定的树 t：
    
       4
      / \
     1   2
    返回 false。

### 递归解法 ###

/**
     * 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 boolean isSubtree(TreeNode s, TreeNode t) {
        
            if (s == null) {
        
                return false;
            }
            return isSubtreeStartWithRoot(s, t) || isSubtree(s.left, t) || isSubtree(s.right, t);
        }
        private boolean isSubtreeStartWithRoot(TreeNode s, TreeNode t) {
        
            if (s == null && t == null) {
        
                return true;
            }
            if (s == null || t == null) {
        
                return false;
            }
            if (s.val != t.val) {
        
                return false;
            }
            return isSubtreeStartWithRoot(s.right, t.right) && isSubtreeStartWithRoot(s.left, t.left);
        }
    }

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

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

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

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

![format_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]: https://imgconvert.csdnimg.cn/aHR0cDovL3dhcmRzZXB0ZW1iZXIuY2x1Yi9Gc2lzMkxhbzF6UkEtUnBic1RFREEwX3owNHdi?x-oss-process=image/format,png