《剑指Offer》二叉树全题——一套妙解，保证让你轻松掌握二叉树~

落日映苍穹つ 2024-04-08 10:56 13阅读 0赞

**目录**

JZ55 二叉树的深度

描述

JZ27 二叉树的镜像

描述

JZ26 树的子结构

描述

JZ79 判断是不是平衡二叉树

描述

JZ28 对称的二叉树

描述

JZ32 从上往下打印二叉树

描述

JZ68 二叉搜索树的最近公共祖先

描述

JZ36 二叉搜索树与双向链表

描述

JZ86 在二叉树中找到两个节点的最近公共祖先

描述

JZ33 二叉搜索树的后序遍历序列

描述

JZ77 按之字形顺序打印二叉树

描述

JZ7 重建二叉树

描述

JZ54 二叉搜索树的第k个节点

描述

JZ82 二叉树中和为某一值的路径(一)

描述

JZ34 二叉树中和为某一值的路径(二)

描述

JZ84 二叉树中和为某一值的路径(三)

描述

JZ78 把二叉树打印成多行

描述

JZ37 序列化二叉树

描述

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

> **注：若一题有多解，并且容易理解，有不啰嗦的办法，我都会罗列出来**

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

## JZ55 二叉树的深度 ##

### 描述 ###

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

数据范围：节点的数量满足 0 \\le n \\le 1000≤n≤100 ，节点上的值满足 0 \\le val \\le 1000≤val≤100

进阶：空间复杂度 O(1)，时间复杂度 O(n)

> 思路：递归左子数和右子数，根节点不为null时，比较左右子树谁大，谁大就累计加一，为空时不累计

public int TreeDepth(TreeNode root) {
            if(root == null){
                return 0;
            }
            int left =  TreeDepth(root.left);
            int right = TreeDepth(root.right);
            return left > right ? left + 1 : right + 1;
        }

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

## JZ27 二叉树的镜像 ##

### 描述 ###

操作给定的二叉树，将其变换为源二叉树的镜像。

数据范围：二叉树的节点数 0 \\le n \\le 10000≤n≤1000 ， 二叉树每个节点的值 0\\le val \\le 10000≤val≤1000

要求： 空间复杂度 O(n) 。本题也有原地操作，即空间复杂度 O(1) 的解法，时间复杂度 O(n)

> 思路：把交换一整个树左右子树想象成交换其中一组左子树和右子树，只要根节点不为空，交换，然后递归左右子树

public TreeNode Mirror (TreeNode pRoot) {
            if(pRoot == null){
                return null;
            }
            swap(pRoot);
            Mirror(pRoot.left);
            Mirror(pRoot.right);
            return pRoot;
        }
        private void swap(TreeNode root){
            TreeNode tmp = root.left;
            root.left= root.right;
            root.right = tmp;
        }

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

## JZ26 树的子结构 ##

### 描述 ###

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

数据范围:

0 <= A的节点个数 <= 10000

0 <= B的节点个数 <= 10000

> 思路：leetcode上有一道和这个很像，也是判断子树是否相同问题，但如果做过leetcode上那道题，你就会发现他们判断的条件不同（空树不是子树）！判读一个树是否为另一个树的子树
> 
> 第一步：先检验子树是否为空，如果为空就没要往后看了，直接返回false。
> 
> 第二步：要判断一个是否一个树为空并且另一个子树不为空的
> 
> 第三步：符合以上条件，再判断两棵树是否相同
> 
> 第四步：如果满足一二条件则递归左树和右树，继续判断

//判断两棵树是否相同
        private boolean sameTree(TreeNode root1,TreeNode root2){
            if(root1 == null && root2 != null){
                return false;
            }
            if(root2 == null){
                return true;
            }
            if(root1.val != root2.val){
                return false;
            }
            return sameTree(root1.left, root2.left) &&
                sameTree(root1.right, root2.right);
        }
        public boolean HasSubtree(TreeNode root1,TreeNode root2) {
            //题中约定空树不为任何一颗树的子结构
            if(root2 == null){
                return false;
            }
            //一个为空，另一个不为空
            if(root1 == null && root2 != null){
                return false;
            }
            return sameTree(root1, root2)||
                HasSubtree(root1.left, root2)||
                HasSubtree(root1.right, root2);
        }

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

## JZ79 判断是不是平衡二叉树 ##

### 描述 ###

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

**平衡二叉树**（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

数据范围：n \\le 100n≤100,树上节点的val值满足 0 \\le n \\le 10000≤n≤1000

要求：空间复杂度O(1)O(1)，时间复杂度 O(n)O(n)

> 思路：判断是否为平衡二叉树，就是看每棵子树是否为平衡二叉树，就要保证每颗子树的高度差不能不能大于1，所以就递归的求出每一颗子树的高度差（求树的深度，上面讲过这道题），一旦不满足，立刻返回false；

//求树的高度
        public int TreeDepth(TreeNode root) {
            if(root == null){
                return 0;
            }
            int left =  TreeDepth(root.left);
            int right = TreeDepth(root.right);
            return left > right ? left + 1 : right + 1;
        }
        public boolean IsBalanced_Solution(TreeNode root) {
            //为空说明到最后也没发现不平衡
            if(root == null){
                return true;
            }
            //每次递归都要保证高度差不能大于1，一旦大于一就没有必要往下走了
            if(Math.abs(TreeDepth(root.left) - TreeDepth(root.right)) > 1){
                return false;
            }
            return IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right);  
        }

##  ##

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

## JZ28 对称的二叉树 ##

### 描述 ###

给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）

数据范围：节点数满足 0 \\le n \\le 10000≤n≤1000，节点上的值满足 |val| \\le 1000∣val∣≤1000

要求：空间复杂度 O(n)，时间复杂度 O(n)

> 思路：判断一颗二叉树是否对称，就是要看他左右子树是否对称，左右子树如果也对称，就要比较左树的左树和右树的右树是否相等，还有左树的右树和右树的左树是否相等，然后递归下去比较

boolean isSymmetrical(TreeNode pRoot) {
            //空也是对称
            if(pRoot == null){
                return true;
            }
            //由于要比较左树和右树，题中所给的一个参数是不够的，所以另用一个函数
            return isSymmetricalChild(pRoot.left, pRoot.right);
        }
        boolean isSymmetricalChild(TreeNode leftTree, TreeNode rightTree){
            //有一方只要为空，而另一方不为空就不是对称
            if(leftTree == null && rightTree != null ||
              leftTree != null && rightTree == null){
                return false;
            }
            //两个都为空
            if(leftTree == null && rightTree == null){
                return true;
            }
            //值不相同直接false
            if(leftTree.val != rightTree.val){
                return false;
            }
            //递归的去比较左树的左树和右树的右树是否相等
            //还有左树的右树和右树的左树是否相等
            return isSymmetricalChild(leftTree.left, rightTree.right) &&
                isSymmetricalChild(leftTree.right, rightTree.left);
        }

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

## JZ32 从上往下打印二叉树 ##

### 描述 ###

不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入\{8,6,10,\#,\#,2,1\}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过)，请你将打印的结果存放到一个数组里面，返回。

数据范围:

0<=节点总数<=1000

\-1000<=节点值<=1000

> 思路：此题可以用递归，也可以用非递归来做，但二叉树的层序遍历按非递归来做的话，更容易理解，可以用一个辅助队列来做此题：（画图更清晰）
> 
> 第一步：建立一个辅助队列，若根节点不为空，则入队；
> 
> 第二部：出队一个元素交给一个指针cur，将其放入顺序表中，同时若他的左子树不为空就入队，右子树也是如此；
> 
> 第三步：循环第二部，直到队列为空；
> 
> 第四步：返回顺序表；

public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
            ArrayList<Integer> array = new ArrayList();
            if(root == null){
                return array;
            }
            //辅助队列
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                //队列只要不为空就弹出一个元素给cur
                TreeNode cur = queue.poll();
                //cur的值放入顺序表
                array.add(cur.val);
                //将cur所指向的结点的左右子树结点若不为空，则入队
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
            }
            return array;
        }

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

## JZ68 二叉搜索树的最近公共祖先 ##

> 此题两个思路（递归与非递归）都很容易理解，所以这里给出两种解法

### 描述 ###

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

1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.

2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值

3.所有节点的值都是唯一的。

4.p、q 为不同节点且均存在于给定的二叉搜索树中。

数据范围:

3<=节点总数<=10000

0<=节点值<=10000

> 解法一（非递归，这个容易想到）：利用搜索二叉树性质，结点值大于p或q的，说明在左边，否则在右边，找到p、q，并用分别用两个顺序表记录下路径，最后顺序表最后的相同一组值，便是公共祖先

public int lowestCommonAncestor (TreeNode root, int p, int q) {
            //用两个顺序表分别记录p,q的路径
            ArrayList<Integer> arrayP = new ArrayList<>();
            ArrayList<Integer> arrayQ = new ArrayList<>();
            //记录一个顺序的值
            Set<Integer> set = new HashSet<>();
            //找p路径，根据二叉搜索树性质
            TreeNode cur = root;
            while(cur != null){
                set.add(cur.val);
                arrayP.add(cur.val);
                if(cur.val > p){
                    cur = cur.left;                
                }else if(cur.val < p){
                    cur = cur.right;
                }else{
                    break;
                }
            }
            //找q路径
            cur = root;
            while(cur != null){
                arrayQ.add(cur.val);
                if(cur.val > q){
                    cur = cur.left;                
                }else if(cur.val < q){
                    cur = cur.right;
                }else{
                    break;
                }
            }
            //从后向前找数据相同的
            int i = 0;
            for(i = arrayQ.size() - 1; i >= 0; i--){
                if(set.contains(arrayQ.get(i))){
                    break;
                }
            }
            return arrayQ.get(i);
        }

> 解法二（递归，不容易想到）：通过利用二叉搜索树的性质，递归时分三种情况
> 
> 情况一：p和q的值都小于根结点，祖先在左边
> 
> 情况二：p和q的值都大于根节点，祖先在右边
> 
> 情况三：q和q的值一个大于等于根节点一个小于等于根节点，那么根节点就是公共祖先，返回即可；

public int lowestCommonAncestor (TreeNode root, int p, int q) {
            //p和q都小于根节点
            if(p < root.val && q < root.val){
                return lowestCommonAncestor(root.left, p, q);
            }
            //p和q的值都大于根结点
            if(p > root.val && q > root.val){
                return lowestCommonAncestor(root.right, p, q);
            }
            //最后一种情况，一个大于一个小于或者等于
            return root.val;
        }

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

## JZ36 二叉搜索树与双向链表 ##

### 描述 ###

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。

数据范围：输入二叉树的节点数 0 \\le n \\le 10000≤n≤1000，二叉树中每个节点的值 0\\le val \\le 10000≤val≤1000  
要求：空间复杂度O(1)（即在原树上操作），时间复杂度 O(n)

注意:

1.要求不能创建任何新的结点，只能调整树中结点指针的指向。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继  
2.返回链表中的第一个节点的指针  
3.函数返回的TreeNode，有左右指针，其实可以看成一个双向链表的数据结构

4.你不用输出双向链表，程序会根据你的返回值自动打印输出

> 分析：此题博主已经专门整理总结出相应博客了，快来看看吧~
> 
> [http://t.csdn.cn/MzPKZ][http_t.csdn.cn_MzPKZ]

TreeNode prev = null;
        public TreeNode createList(TreeNode root){
            if(root == null){
                return null;
            }
            createList(root.left);
            root.left = prev;
            if(prev != null){
                prev.right = root;
            }
            prev = root;
            createList(root.right);
            return root;//最后返回根结点
        }
        public TreeNode Convert(TreeNode pRootOfTree) {
            if(pRootOfTree == null){
                return null;
            }
            TreeNode head = createList(pRootOfTree);
            //需要遍历到链表的头节点
            while(head.left != null){
                head = head.left;
            }
            return head;
        }

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

## JZ86 在二叉树中找到两个节点的最近公共祖先 ##

> 此题两个思路（递归与非递归）都很容易理解，所以这里给出两种解法。

### 描述 ###

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

数据范围：树上节点数满足 1 \\le n \\le 10^5 \\1≤n≤105 , 节点值val满足区间 \[0,n)

要求：时间复杂度 O(n)

注：本题保证二叉树中每个节点的val值均不相同。

> 解法一（纯递归）：分三种情况，第一是两节点都在根节点左侧，第二是，两节点都在根节点右侧，第三是两节点分别在根节点的两侧，所以只需要递归的去找结点，若只在根节点的左侧找到结点，右侧为空，说明左侧结点即为公共祖先，反之亦然，若在根节点的左右都不为空，说明根节点就是公共祖先

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
            return func(root, o1, o2).val;
        }
        private TreeNode func(TreeNode root, int o1, int o2){
            if(root == null){
                return null;
            }
            //递归的过程若找到，就返回他
            if(root.val == o1 || root.val == o2){
                return root;
            }
            //分别去递归左右
            TreeNode left = func(root.left, o1, o2);
            TreeNode right = func(root.right, o1, o2);
            //分别在两边的情况，那么根节点就是公共祖先
            if(left != null && right != null){
                return root;
            }
            //只在一边找到
            else if(left != null){
                return left;
            }else{
                return right;
            }
        }

> 解法二（双栈+递归）：可以创建两个栈，通过两个栈分别来记录从根节点到达两节点的路径，得到路径后，比较哪个栈大，多的一方出栈，直到两栈大小持平，再同时出栈，如果出栈的元素相同，即为公共祖先

public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
            return func(root, o1, o2).val;
        }
        private TreeNode func(TreeNode root, int p, int q){
            Stack<TreeNode> stackP = new Stack<>();
            Stack<TreeNode> stackQ = new Stack<>();
            //找路径
            fundPath(root, stackP, p);
            fundPath(root, stackQ, q);
            //比较两个路径谁长，长的一方出栈，直到持平
            while(stackP.size() > stackQ.size()){
                stackP.pop();
            }
            //比较两个路径谁长，长的一方出栈，直到持平
            while(stackP.size() < stackQ.size()){
                stackQ.pop();
            }
            //然后同时出栈,遇到相同的就停下，说明就是公共祖先
            while(stackP.peek() != stackQ.peek()){
                stackP.pop();
                stackQ.pop();
            }
            return stackP.peek();
        }
        private boolean fundPath(TreeNode root,Stack<TreeNode> stack, int val){
            if(root == null){
                return false;
            }
            //进来先压栈
            stack.push(root);
            if(root.val == val){
                return true;
            }
            //没找就递归下去
            boolean left = fundPath(root.left, stack, val);
            if(left){
                return true;
            }
            boolean right = fundPath(root.right, stack, val);
            if(right){
                return true;
            }
            //左右两边都没找到，说明此根节点不是路径，弹出即可
            stack.pop();
            return false;
        }

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

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

### 描述 ###

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

数据范围： 节点数量 0 \\le n \\le 10000≤n≤1000 ，节点上的值满足 1 \\le val \\le 10^\{5\}1≤val≤105 ，保证节点上的值各不相同  
要求：空间复杂度 O(n)O(n) ，时间时间复杂度 O(n^2)O(n2)

提示：

1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。

2.该题我们约定空树不是二叉搜索树

3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历

思路：逆序遍历你中所给的数组，就可以得到根结点 -> 右结点 -> 左结点，可以根据二叉搜索树的性质，左<根<右，所以第 i 元素若小于第 i + 1元素说明这下一个元素便是右结点，反之，i+1结点已经是后面最大的结点，故要满足 大于 i + 1 的后面的元素都要比根节点小，具体实现在注释里

public boolean VerifySquenceOfBST(int [] array) {
            //要求空树不是二叉搜索树
            int len = array.length;
            if(len == 0){
                return false;
            }
            Stack<Integer> stack = new Stack<>();
            //用最大值先维护根节点
            int root = Integer.MAX_VALUE;
            //根->右->左
            for(int i = len - 1; i >= 0; i--){
                //已经确定目前数组中只含左子树，若左子树大于根节点，就不符合
                if(array[i] > root){
                    return false;
                }
                //array[i]的值一旦小于前一项，说明进入左子树
                //在栈不为空的情况下弹出给root，为左子树的根结点
                while(!stack.isEmpty() && array[i] < stack.peek()){
                    root = stack.pop();
                }
                //每个元素都要入栈一次
                stack.push(array[i]);
            }
            //没有违反规则
            return true;
        }

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

## JZ77 按之字形顺序打印二叉树 ##

### 描述 ###

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

数据范围：0 \\le n \\le 15000≤n≤1500,树上每个节点的val满足 |val| <= 1500∣val∣<=1500  
要求：空间复杂度：O(n)，时间复杂度：O(n)

> 思路：一种非常容易理解的办法，博主已经整理出博客了，快来看看吧~
> 
> [http://t.csdn.cn/43ajY][http_t.csdn.cn_43ajY]

public ArrayList<ArrayList<Integer> > Print(TreeNode root) {
            ArrayList<ArrayList<Integer>> retArray = new ArrayList<>();
            if(root == null){
                return retArray;
            }
            List<TreeNode> list = new LinkedList<>();
            //负责确定奇数还是偶数
            int count = 1;
            list.add(root);
            while(!list.isEmpty()){
                ArrayList<Integer> array = new ArrayList<>();
                //如果是奇数，每次从左往右入顺序表
                if(count % 2 != 0){
                    for(int start = 0; start < list.size(); start++){
                        array.add(list.get(start).val);
                    }
                }else{//偶数从右往左
                    for(int end = list.size() - 1; end >= 0; end--){
                        array.add(list.get(end).val);
                    }
                }
                //输入后入二维顺序表
                ArrayList<Integer> tmpArray = new ArrayList<>(array);
                retArray.add(tmpArray);
                //每次都删除零下标位置
                int tmp = 0;
                int row = list.size();
                while(!list.isEmpty() && tmp < row){
                    TreeNode key = list.remove(0);
                    //将key的左右结点放入链表
                    if(key.left != null){
                        list.add(key.left);
                    }
                    if(key.right != null){
                        list.add(key.right);
                    }
                    tmp++;
                }
                //去下一行
                count++;
            }
            return retArray;
        }

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

## JZ7 重建二叉树 ##

### 描述 ###

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。

> 思路：其实此题就是让你根据前序遍历和中序遍历的来构建二叉树，博主已经整理出博客啦~不光告诉你如何根据前序遍历和中序遍历如何构建二叉树，并且还教你如何根据中序遍历和后序遍历来构建二叉树~
> 
> [http://t.csdn.cn/q5BIJ][http_t.csdn.cn_q5BIJ]

public int preIndex = 0;
     public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBegan, int inEnd)                                
        {
            //如果ib > ie说明递归终止
            if(inBegan > inEnd){
                return null;
            }
            //创建根节点
            TreeNode root = new TreeNode(preorder[preIndex]);
            //在中序遍历中找到对应的根节点下标
            int InorderIndex = fundInorderIndex(inorder, preorder[preIndex], inBegan, inEnd);
            //前序遍历中的下标继续往后遍历
            preIndex++;
            //通过递归继续创建左子树和右子树
            root.left = buildTreeChild(preorder, inorder, inBegan, InorderIndex - 1);
            root.right = buildTreeChild(preorder, inorder, InorderIndex + 1, inEnd);
            //最后返回根结点即可
            return root;
        }
        public int fundInorderIndex(int[] inorder, int val, int inBegan, int inEnd){
            for(int i = inBegan; i <= inEnd; i++){
                if(inorder[i] == val){
                    return i;
                }
            }
            return -1;
        }
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
        }

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

## JZ54 二叉搜索树的第k个节点 ##

### 描述 ###

给定一棵结点数为n 二叉搜索树，请找出其中的第 k 小的TreeNode结点值。

1.返回第k小的节点值即可

2.不能查找的情况，如二叉树为空，则返回-1，或者k大于n等等，也返回-1

3.保证n个节点的值不一样

数据范围： 0 \\le n \\le10000≤n≤1000，0 \\le k \\le10000≤k≤1000，树上每个结点的值满足0 \\le val \\le 10000≤val≤1000  
进阶：空间复杂度 O(n)，时间复杂度 O(n)

> 思路：对于二叉搜索树而言，中序遍历就可以得到升序序列，所以直接拿第k个元素即可

//记录递归次数
        private int count = 0;
        //记录第k小数字
        private int ret = -1;
        public int KthNode (TreeNode root, int k) {
            fundMin(root, k);
            if(ret != -1){
                return ret;
            }else{
                return -1;
            }
        }
        private void fundMin(TreeNode root, int k){
            if(root == null || count > k){
                return;
            }
            fundMin(root.left, k);
            count++;
            //遇到第k小就修改
            if(count == k){
                ret = root.val;
            }
            fundMin(root.right, k);
        }

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

## JZ82 二叉树中和为某一值的路径(一) ##

### 描述 ###

给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

> 思路（注意一定要看清题目描述，是从根往下一直到叶子结点）：递归遍历此树，每到下一个结点，sum就减去相应的val值，一旦发现是叶子结点，判断sum是否为0，若为零说明正确

public boolean hasPathSum (TreeNode root, int sum) {
            if(root == null){
                return false;
            }
            //进入叶子结点
            if(root.left == null && root.right == null && sum - root.val == 0){
                return true;
            }
            //不满足以上两点，才继续递归
            return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
        }

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

## JZ34 二叉树中和为某一值的路径(二) ##

### 描述 ###

输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

> 思路：递归遍历二叉树，从根节点开始记录，若到了叶子结点且路径正确，则保存此路径，并回溯到上一个结点，继续查看其他结点是否正确，若到了叶子结点且路径不正确，则不保留，同样回溯到上结点，继续查看其他结点

private ArrayList<ArrayList<Integer>> retArray = new ArrayList<>();
        private ArrayList<Integer> array = new ArrayList<>();
        //寻找正确路径
        private void fundPath(TreeNode root, int sum){
            if(root == null){
                return;
            }
            array.add(root.val);
            //路径到了叶子结点
            if(root.left == null && root.right == null && sum - root.val == 0){
                //若进来了，说明此路径正确，加入到二维顺序表中
                retArray.add(new ArrayList<>(array));
            }
            //递归左右树
            fundPath(root.left, sum - root.val);
            fundPath(root.right, sum - root.val);
            //到了这里，说明不是正确路径，删除上一个元素
            array.remove(array.size() - 1);
        }
        public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int expectNumber) {
            fundPath(root, expectNumber);
            return retArray;
        }

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

## JZ84 二叉树中和为某一值的路径(三) ##

### 描述 ###

给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。

1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点

2.总节点数目为n

3.保证最后返回的路径个数在整形范围内(即路径个数小于231-1)

数据范围:

0<=n<=10000<=n<=1000

\-10^9<=节点值<=10^9−109<=节点值<=109

> 思考：此题很容易，但一定要注意读题！一定要注意读题！一定要注意读题！博主刚开始还以为测试用例出错了（做完此题同样的另外两个版本，形成思维定势），最后仔细读题才发现，题目的要求是，不需要一定从根节点开始，也不需要一定由叶子结点结束，也就是说，每个结点都可以作为开始，所以，首先需要递归遍历二叉树，因为每一个结点都有可能是开始结点，每次递归得到一个结点就再顺着这个结点递归寻找路径即可，用一个计数器记录下正确路径，最后返回即可~

//计数器
        private int count = 0;
        public int FindPath (TreeNode root, int sum) {
            if(root == null){
                return count;
            }
            //每一个结点都可以作为根结点开始
            fundPath(root, sum);
            FindPath(root.left, sum);
            FindPath(root.right, sum);
            return count;
        }
        public void fundPath(TreeNode root, int sum){
            if(root == null){
                return;
            }
            //满足则计数器就加一
            if(sum - root.val == 0){
                count++;
            }
            //递归左右结点
            fundPath(root.left, sum - root.val);
            fundPath(root.right, sum - root.val);
        }

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

## JZ78 把二叉树打印成多行 ##

### 描述 ###

给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。

> 思路（之字型打印二叉树的简易版，当时为了便于理解所以用的双向链表来解，由于之前讲过了，此题咱就来用队列，也是最佳办法）：实际上是对二叉树的层序遍历，并将每一层数据放入二维顺序表；此题可以用一个辅助队列，来记录每一行的数据，怎么记录每一行的长度呢（难点）？每次先求出队列长度，控制把这一层所有的结点的子结点入队，这样往复，每层的结点就能被记录下来~

ArrayList<ArrayList<Integer> > Print(TreeNode root) {
            //此题说白了就是层序遍历，并记录每一层数据
            ArrayList<ArrayList<Integer>> retArray = new ArrayList<>();
            //若为空，直接返回
            if(root == null){
                return retArray;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            //先将根节点入队
            queue.offer(root);
            while(!queue.isEmpty()){
                ArrayList<Integer> array = new ArrayList<>();
                //记录每层的长度
                int len = queue.size();
                //有几个结点，就让每个结点的子结点放入队列
                for(int i = 0; i < len; i++){
                    TreeNode tmp = queue.poll();
                    //放入顺序表
                    array.add(tmp.val);
                    //若子节点不是空指针则将子节点放入队列
                    if(tmp.left != null){
                        queue.offer(tmp.left);
                    }
                    if(tmp.right != null){
                        queue.offer(tmp.right);
                    }
                }
                //将每一层放入二维顺序表
                retArray.add(array);
            }
            return retArray;
        }

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

## JZ37 序列化二叉树 ##

### 描述 ###

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（\#）  
二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

> 思路：
> 
> 第一个序列化：类似于上一题的（JZ78 把二叉树打印成多行）层序遍历，思想也是一样的，只需要把得到的数字转化成字符串类型，并返回即可；
> 
> 第二个反序列化：实际上如何序列化，反序列化思路也差不多，依旧是从队列中取值，并从序列化中截取两值是否为"Null"，之后循环即可；

String Serialize(TreeNode root) {
            //层序遍历
            StringBuilder stringBuilder = new StringBuilder();
            //防止为空
            if(root == null){
                return stringBuilder.toString();
            }
            //用队列辅助序列化
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                TreeNode tmp = queue.poll();
                if(tmp != null){
                    stringBuilder.append(tmp.val);
                    stringBuilder.append(",");
                    queue.offer(tmp.left);
                    queue.offer(tmp.right);
                }else{
                    stringBuilder.append("Null,");
                }
            }
            return stringBuilder.toString();
        }
        TreeNode Deserialize(String str) {
            if(str==null||str.length()==0){
                return null;
            }
            String[] sb=str.split("\\,");
            TreeNode root=new TreeNode(Integer.parseInt(sb[0]));
            Queue<TreeNode> queue=new LinkedList<>();
            queue.offer(root);
            int i=1;    //字符串数组下标
            while(!queue.isEmpty()){
                TreeNode temp=queue.poll();
                if(!sb[i].equals("Null")){
                    temp.left=new TreeNode(Integer.parseInt(sb[i]));
                    queue.offer(temp.left);
                }
                i++;
                if(!sb[i].equals("Null")){
                    temp.right=new TreeNode(Integer.parseInt(sb[i]));
                    queue.offer(temp.right);
                }
                i++;
            }
            return root;
        }

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

![f92e9ced893c4cae91782939d71f346f.gif][]

**讲真，肝疼...**

[http_t.csdn.cn_MzPKZ]: http://t.csdn.cn/MzPKZ
[http_t.csdn.cn_43ajY]: http://t.csdn.cn/43ajY
[http_t.csdn.cn_q5BIJ]: http://t.csdn.cn/q5BIJ
[f92e9ced893c4cae91782939d71f346f.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/08/0fb6d577b9694dadbc306c4986508abf.gif