剑指Offer——树(一)

﹏ヽ暗。殇╰゛Y 2023-03-02 07:51 4阅读 0赞

### 文章目录 ###

*   *  剑指 Offer 07. 重建二叉树
     *   *  递归
         *  迭代
     *  剑指 Offer 26. 树的子结构
     *   *  递归
     *  剑指 Offer 27. 二叉树的镜像
     *   *  递归解法
     *  剑指 Offer 28. 对称的二叉树
     *   *  递归解法
         *  迭代解法
     *  剑指 Offer 32 - I. 从上到下打印二叉树
     *   *  解法
     *  剑指 Offer 32 - II. 从上到下打印二叉树 II
     *   *  层序遍历
     *  剑指 Offer 32 - III. 从上到下打印二叉树 III
     *   *  层序遍历
         *   *  推荐阅读

## 剑指 Offer 07. 重建二叉树 ##

[剑指 Offer 07. 重建二叉树][Offer 07.]

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出
    
    前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7]
    返回如下的二叉树：
    
        3
       / \
      9  20
        /  \
       15   7
     
    
    限制：
    
    0 <= 节点个数 <= 5000

### 递归 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        private Map<Integer, Integer> indexMap;
        private TreeNode myBuildTree(int[] preorder, int[] inorder, int preorderLeft, int preorderRight, int inorderLeft, int inorderRight) {
        
            if (preorderLeft > preorderRight) {
        
                return null;
            }
            // 前序遍历中的第一个节点就是根节点
            int preoderRoot = preorderLeft;
            // 在中序遍历中定位根节点
            int inorderRoot = indexMap.get(preorder[preorderLeft]);
            TreeNode root = new TreeNode(preorder[preorderLeft]);
            // 得到左子树中的节点数目
            int sizeLeftSubtree = inorderRoot - inorderLeft;
            // 递归地构造左子树，并连接到根节点
            // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
            root.left = myBuildTree(preorder, inorder, preorderLeft + 1, preorderLeft + sizeLeftSubtree, inorderLeft, inorderRoot - 1);
            root.right = myBuildTree(preorder, inorder, preorderLeft + sizeLeftSubtree + 1, preorderRight, inorderRoot + 1, inorderRight);
            return root;
        }
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        
            int n = preorder.length;
            indexMap = new HashMap<>();
            // 构造哈希映射，帮助我们快速定位根节点
            for (int i = 0; i < n; i++) {
        
                indexMap.put(inorder[i], i);
            }
            return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
        } 
    }

### 迭代 ###

详解见[https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/][https_leetcode-cn.com_problems_construct-binary-tree-from-preorder-and-inorder-traversal_solution_cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9]

class Solution {
        
        public TreeNode buildTree(int[] preorder, int[] inorder) {
        
            if (preorder == null || preorder.length == 0) {
        
                return null;
            }
            TreeNode root = new TreeNode(preorder[0]);
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(root);
            int inorderIndex = 0;
            for (int i = 1; i < preorder.length; i++) {
        
                int preorderVal = preorder[i];
                TreeNode node = stack.peek();
                if (node.val != inorder[inorderIndex]) {
        
                    node.left = new TreeNode(preorderVal);
                    stack.push(node.left);
                } else {
        
                    while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
        
                        node = stack.pop();
                        inorderIndex++;
                    }
                    node.right = new TreeNode(preorderVal);
                    stack.push(node.right);
                }
            }
            return root;
        }
    }

## 剑指 Offer 26. 树的子结构 ##

[剑指 Offer 26. 树的子结构][Offer 26.]

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
    给定的树 A:
    
         3
        / \
       4   5
      / \
     1   2
    给定的树 B：
    
       4 
      /
     1
    返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
    
    示例 1：
    
    输入：A = [1,2,3], B = [3,1]
    输出：false
    示例 2：
    
    输入：A = [3,4,5,1,2], B = [4,1]
    输出：true
    限制：
    
    0 <= 节点个数 <= 10000

### 递归 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public boolean isSubStructure(TreeNode A, TreeNode B) {
        
            return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
        }
        boolean recur(TreeNode A, TreeNode B) {
        
            if (B == null) {
        
                return true;
            }
            if (A == null || A.val != B.val) {
        
                return false;
            }
            return recur(A.right, B.right) && recur(A.left, B.left);
        }
    }

## 剑指 Offer 27. 二叉树的镜像 ##

[剑指 Offer 27. 二叉树的镜像][Offer 27.]

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

例如输入：
    
         4
       /   \
      2     7
     / \   / \
    1   3 6   9
    镜像输出：
    
         4
       /   \
      7     2
     / \   / \
    9   6 3   1
    
     
    
    示例 1：
    
    输入：root = [4,2,7,1,3,6,9]
    输出：[4,7,2,9,6,3,1]
     
    
    限制：
    
    0 <= 节点个数 <= 1000

### 递归解法 ###

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

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

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

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
    
        1
       / \
      2   2
     / \ / \
    3  4 4  3
    但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
    
        1
       / \
      2   2
       \   \
       3    3
    
     
    
    示例 1：
    
    输入：root = [1,2,2,3,4,4,3]
    输出：true
    示例 2：
    
    输入：root = [1,2,2,null,3,null,3]
    输出：false
     
    
    限制：
    
    0 <= 节点个数 <= 1000

### 递归解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            if (root == null) {
        
                return true;
            }
            return isSymmetric(root.left, root.right);
        }
        private boolean isSymmetric(TreeNode t1, TreeNode t2) {
        
            if (t1 == null && t2 == null) {
        
                return true;
            }
            if (t1 == null || t2 == null) {
        
                return false;
            }
            if (t1.val != t2.val) {
        
                return false;
            }
            return isSymmetric(t1.left, t2.right) && isSymmetric(t1.right, t2.left);
        }
    }

### 迭代解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public boolean isSymmetric(TreeNode root) {
        
            if (root == null) {
        
                return true;
            }
            return isSymmetric(root.left, root.right);
        }
        public boolean isSymmetric(TreeNode t1, TreeNode t2) {
        
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(t1);
            queue.offer(t2);
            while (!queue.isEmpty()) {
        
                t1 = queue.poll();
                t2 = queue.poll();
                if (t1 == null && t2 == null) {
        
                    continue;
                }
                if (t1 == null || t2 == null || t1.val != t2.val) {
        
                    return false;
                }
                queue.offer(t1.left);
                queue.offer(t2.right);
                queue.offer(t1.right);
                queue.offer(t2.left);
            }
            return true;
        }
    }

## 剑指 Offer 32 - I. 从上到下打印二叉树 ##

[剑指 Offer 32 - I. 从上到下打印二叉树][Offer 32 - I.]

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如:
    给定二叉树: [3,9,20,null,null,15,7],
    
        3
       / \
      9  20
        /  \
       15   7
    返回：
    
    [3,9,20,15,7]
     
    
    提示：
    
    节点总数 <= 1000

### 解法 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public int[] levelOrder(TreeNode root) {
        
            if (root == null) {
        
                return new int[0];
            }
            Queue<TreeNode> queue = new LinkedList<>();
            List<Integer> list = new ArrayList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
        
                    queue.offer(node.left);
                }
                if (node.right != null) {
        
                    queue.offer(node.right);
                }
            }
            int[] res = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
        
                res[i] = list.get(i);
            }
            return res;
        } 
    }

## 剑指 Offer 32 - II. 从上到下打印二叉树 II ##

[剑指 Offer 32 - II. 从上到下打印二叉树 II][Offer 32 - II. _ II]

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:
    给定二叉树: [3,9,20,null,null,15,7],
    
        3
       / \
      9  20
        /  \
       15   7
    返回其层次遍历结果：
    
    [
      [3],
      [9,20],
      [15,7]
    ]
     
    
    提示：
    
    节点总数 <= 1000

### 层序遍历 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            List<List<Integer>> res = new ArrayList<>();
            if (root == null) {
        
                return res;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                int size = queue.size();
                List<Integer> list = new ArrayList<>();
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = queue.poll();
                    list.add(node.val);
                    if (node.left != null) {
        
                        queue.add(node.left);
                    }
                    if (node.right != null) {
        
                        queue.add(node.right);
                    }
                }
                res.add(list);
            }
            return res;
        }
    }

## 剑指 Offer 32 - III. 从上到下打印二叉树 III ##

[剑指 Offer 32 - III. 从上到下打印二叉树 III][Offer 32 - III. _ III]

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如:
    给定二叉树: [3,9,20,null,null,15,7],
    
        3
       / \
      9  20
        /  \
       15   7
    返回其层次遍历结果：
    
    [
      [3],
      [20,9],
      [15,7]
    ]
     
    
    提示：
    
    节点总数 <= 1000

### 层序遍历 ###

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public List<List<Integer>> levelOrder(TreeNode root) {
        
            List<List<Integer>> res = new ArrayList<>();
            if (root == null) {
        
                return res;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
        
                int size = queue.size();
                List<Integer> list = new ArrayList<>();
                for (int i = 0; i < size; i++) {
        
                    TreeNode node = queue.poll();
                    list.add(node.val);
                    if (node.left != null) {
        
                        queue.add(node.left);
                    }
                    if (node.right != null) {
        
                        queue.add(node.right);
                    }
                }
                if (res.size() % 2 == 1) {
        
                    Collections.reverse(list);
                }
                res.add(list);
            }
            return res;
        }
    }

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

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

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

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

![format_png][]

[Offer 07.]: https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/
[https_leetcode-cn.com_problems_construct-binary-tree-from-preorder-and-inorder-traversal_solution_cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9]: https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/
[Offer 26.]: https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
[Offer 27.]: https://leetcode-cn.com/problems/er-cha-shu-de-jing-xiang-lcof/
[Offer 32 - I.]: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof/
[Offer 32 - II. _ II]: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-ii-lcof/
[Offer 32 - III. _ III]: https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof/
[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]: /images/20230208/b92cda97dafe4ea9a153b723a5e64986.png