剑指offer刷题总结——树篇（一）

谁践踏了优雅 2021-09-21 03:14 343阅读 0赞

> 星级：2

### 1.重建二叉树 ###

**【题目】**

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 \{1,2,4,7,3,5,6,8\} 和中序遍历序列 \{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

**【代码】**

package swear2offer.tree;
    
    public class ReCreateTree { 
    
        /** * 前序遍历序列 {1,2,4,7,3,5,6,8} * 中序遍历序列 {4,7,2,1,5,3,8,6} * * 思路： * 需要考虑递归的方式，本身树这一结构就很适合进行递归 * 前序是 根、左、右 * 中序是 左、右、根 * 然后用递归的方式把左右节点放置在根节点之下 * */
        public TreeNode reConstructBinaryTree(int [] pre,int [] in) { 
    
            return CreateTree(pre,0, pre.length,in,0,in.length);
        }
    
        public TreeNode CreateTree(int[] pre, int pStart,int pEnd,int[] in,int iStart,int iEnd) { 
    
            if (pStart>pEnd || iStart>iEnd ) return null;
    
            if (pStart>=pre.length|| iStart>=in.length) return null;
    
            int rootIndex,leftSize,rightSize;
    
            TreeNode root = new TreeNode(pre[pStart]);
    
            // 根节点在中序序列的下标
            rootIndex = GetIndex(in,root.val);
    
            // 左子树长度
            leftSize = rootIndex - iStart;
            // 右子树长度
            rightSize = iEnd - rootIndex;
    
            // 左子树
            root.left = CreateTree(pre,pStart+1,pStart+leftSize,
                            in,iStart,rootIndex-1);
            // 右子树
            root.right = CreateTree(pre,pStart+leftSize+1,pEnd,
                    in,rootIndex+1,iEnd);
    
            return root;
        }
    
        public int GetIndex(int[] a, int target) { 
    
            for(int i=0; i<a.length; i++) { 
                if (a[i] == target) { 
                    return i;
                }
            }
            return -1;
        }
    
        public static void main(String[] args) { 
            int[] pre = { 1,2,4,7,3,5,6,8};
            int[] in = { 4,7,2,1,5,3,8,6};
            TreeNode node = new ReCreateTree().reConstructBinaryTree(pre,in);
            System.out.println(node);
        }
    }

**【思路】**

这类问题只需要用代码实现解决问题的过程即可，但是需要注意的是\*\*，递归的跳出和数组边界越界\*\*的问题，因为随着左边界不断右移，必然会出现越界的情况，需要在递归原有的跳出条件上加上越界判断。

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

### 2.树的子结构 ###

**【题目】**

输入两棵二叉树 A，B，判断 B 是不是 A 的子结构。（ps：我们约定空树不是任意一个树的子结构）

**【代码】**

package swear2offer.tree;
    
    
    public class SubTree { 
    
        /** * 输入两棵二叉树 A，B，判断 B 是不是 A 的子结构。 * （ps：我们约定空树不是任意一个树的子结构） * */
        //1. 创建一个辅助函数判断两棵树是否相等 2. 递归遍历 A 树的每一个节点作为根结点和 B 树进行比较
        public boolean isSubStructure(TreeNode A, TreeNode B) { 
            if(A == null || B == null) return false;
            return dfs(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
        }
        public boolean dfs(TreeNode A, TreeNode B){ 
            if(B == null) return true;
            if(A == null) return false;
            return A.val == B.val && dfs(A.left, B.left) && dfs(A.right, B.right);
        }

**【思路】**

子树和子结构，是两种概念，需要区分：

**（一）子树**

一棵大树 A，一棵小树 B，若 B 是 A 的子树，则：

*  B 和 A 的结点值完全相同，它们俩的左子树、右子树所有结点的值也完全相同
 *  或者 B 的左孩子和 A 的结点值完全相同，它们俩的左子树、右子树所有结点的值也完全相同
 *  或者 B 的右孩子和 A 的结点值完全相同，它们俩的左子树、右子树所有结点的值也完全相同

举个形象的例子：子树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]  
这棵大树的子树有：

*  4 和 5 对应的两棵子树
 *  3 本身自己完整的一棵树

**而里面的小框圈出来的不是 3 这棵大树的子树！**

**（二）子结构**

还是上面那张图，子结构就是不用那么严格，图中的小框就是整棵树的子结构，图中的黄色大框也是整棵树的子结构，所以只要找到符合树的一部分树结点即可

可以看到，子结构的判断就是 “没那么严格” 了，和**判断子树的写法就是一行代码不同而已，值不想等的时候不直接返回 false，继续往树的右结点和左结点找，找的一个相等值的结点就好**，但如果你 一旦找到了结点值是相等的，那么久要保证这两个数的结点值要一一对应上了！

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

### 3.二叉树的镜像 ###

**【题目】**

操作给定的二叉树，将其变换为源二叉树的镜像。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]  
**【代码】**

package swear2offer.tree;
    
    import java.util.LinkedList;
    import java.util.Queue;
    
    public class Mirror { 
    
        // 队列存储树的节点
        Queue<TreeNode> queue = new LinkedList<>();
    
        /** * 操作给定的二叉树，将其变换为源二叉树的镜像。 * * 思路： * 先把交换父节点，在交换子节点，从上往下交换，需要队列辅助实现 * */
        public void Mirror(TreeNode root) { 
            if (root == null) return;
    
            TreeNode node,temp;
            queue.add(root);
    
            while (!queue.isEmpty()) { 
                // 获得队列首元素
                node = queue.remove();
    
                // 把左右子树加入队列
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
    
                // 交换子树
                temp = node.right;
                node.right = node.left;
                node.left = temp;
            }
        }
    }

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

### 4.从上往下打印二叉树 ###

**【题目】**

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

**【代码】**

/** * 从上往下打印出二叉树的每个节点，同层节点从左至右打印。 * */
        public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) { 
    
            ArrayList<Integer> list = new ArrayList<>();
    
            if (root == null) return list;
    
            Queue<TreeNode> q = new LinkedList<>();
    
            q.add(root);
            list.add(root.val);
    
            TreeNode node;
    
            while (!q.isEmpty()) { 
                node = q.remove();
    
                // 把左右子树加入队列
                if (node.left != null) { 
                    q.add(node.left);
                    list.add(node.left.val);
                }
                if (node.right != null) { 
                    q.add(node.right);
                    list.add(node.right.val);
                }
            }
    
            return list;
    
        }

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

### 5.二叉搜索树的后序遍历序列 ###

**【题目】**

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出 Yes, 否则输出 No。假设输入的数组的任意两个数字都互不相同。

**【代码】**

/** * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。 * 如果是则输出 Yes, 否则输出 No。假设输入的数组的任意两个数字都互不相同。 * * 以最后一个元素为支点，判断左半部分是否都小于支点，右半部分是否大于支点 * */
        public boolean VerifySquenceOfBST(int [] sequence) { 
    
            int n;
    
            n = sequence.length;
    
            if (n == 0) return false;
    
            return Judge(sequence,0,n-1);
    
        }
    
        public boolean Judge (int[] a, int start, int end) { 
            if (start >= end) return true;
    
            int pivot,i,j;
    
            pivot = a[end];
    
            // 找到大于支点的下标
            for (i = start; i<end; i++) { 
                if (a[i]>pivot) { 
                    break;
                }
            }
    
            // 序列中存在大于支点的元素
            if (i<end) { 
    
                // 大于支点的元素后面，如果存在小于支点的元素，则不正确
                for (j=i; j<end; j++) { 
                    if (a[j]<pivot) return false;
                }
    
                return Judge(a,start,i-1) && Judge(a,i,end-1);
    
            } else { 
                return Judge(a,start,end-1);
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]: /images/20210920/97b7598d887243b8acba2664d35f6f71.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]: /images/20210920/2532d9bc185046aa889db4c3478d4fbc.png