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

星级：1

1.二叉树中和为某一值的路径

【题目】

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

【代码】

	/**
     * 输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
     * 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
     * (注意：在返回值的 list 中，数组长度大的数组靠前)
     *
     * 思路：
     * 保存所有路径，并把路径长度放在首位，然后在进行删除和排序
     * 经过测试，上面这种方式不可行，因为需要递归的结果来循环找从叶子节点的序列，
     * 但是递归返回的ArrayList是不断变化的，而ArrayList对于变化的序列是不可操作的
     * 会抛出并发修改异常
     *
     * 这种不可行的方式是从下往上回溯，需要遍历叶子节点，在添加根节点
     * 那么，从根节点往叶子节点的上到下的回溯方式，不需要遍历
     *
     * 思路2：
     * 可以对target进行操作，每次减去root的val，对target==0以及是否到达叶子节点判断
     *
     * 补充：
     * 对于这种返回值的递归，需要与跳出条件进行区分，
     * 输入值为空和递归的跳出条件，如果不一致，通常需要另起一个方法
     * */
	
	ArrayList<ArrayList<Integer>> paths = new ArrayList<>();
    ArrayList<Integer> path = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if (root == null || target == 0) return new ArrayList<>();

        Find(root,target,paths,path);

        return paths;
    }

    /**
     * 回溯的思想，
     * 通过递归，把不正确的值还原
     * */
    public void Find(TreeNode root, int target,
                     ArrayList<ArrayList<Integer>> paths, ArrayList<Integer> path) {

        if (root == null) return;

        // 创建path的副本，并且把root加入其中
        path.add(root.val);
        target -= root.val;

        // 不符合条件
        if (target < 0) return;

        // 到达叶子节点并且target符合
        if (target == 0 && root.left == null && root.right == null) {
            // 找到一条符合条件的路径并返回
            paths.add(path);
            return;
        }

        Find(root.left,target,paths,new ArrayList<>(path));
        Find(root.right,target,paths,new ArrayList<>(path));
    }

【思考】

• 保存所有路径，并把路径长度放在首位，然后在进行删除和排序
  经过测试，上面这种方式不可行，因为需要递归的结果来循环找从叶子节点的序列，
  但是递归返回的ArrayList是不断变化的，而ArrayList对于变化的序列是不可操作的
  会抛出并发修改异常

• 这种不可行的方式是从下往上回溯，需要遍历叶子节点，在添加根节点
  那么，从根节点往叶子节点的上到下的回溯方式，不需要遍历

• 思路2：
  可以对target进行操作，每次减去root的val，对target==0以及是否到达叶子节点判断

• 补充：
  对于这种返回值的递归，需要与跳出条件进行区分，
  输入值为空和递归的跳出条件，如果不一致，通常需要另起一个方法

• 补充2：
  多路径保存，对于arraylist这种，可以在构造函数传入一个已经存在的arraylist，相当于深复制。

2.二叉搜索树与双向链表

【题目】

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

【代码】

public TreeNode Convert(TreeNode pRootOfTree) {

        if (pRootOfTree == null) return null;

        if (pRootOfTree.left == null && pRootOfTree.right == null)
            return pRootOfTree;

        TreeNode left,right,temp;

        left = Convert(pRootOfTree.left);
        right = Convert(pRootOfTree.right);

        // 右节点不为空
        if (right != null) {
            pRootOfTree.right = right;
            right.left = pRootOfTree;
        }

        if (left == null) {
            return pRootOfTree;
        } else {
            temp = left;
            while (temp.right != null) temp = temp.right;

            temp.right = pRootOfTree;
            pRootOfTree.left = temp;

            return left;
        }

    }

【思考】

注意判断返回为空的情况，连接左右子树的时候，需要考虑是否存在左右子树。

3.二叉树的深度

【题目】

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

【代码】

	/**
     *
     * 输入一棵二叉树，求该树的深度。
     * 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，
     * 最长路径的长度为树的深度。
     * */
    public int TreeDepth(TreeNode root) {
        if (root == null) return 0;

        int left,right,high;

        left = TreeDepth(root.left);
        right = TreeDepth(root.right);

        high = left > right ? left : right;

        return high + 1;
    }

【思考】

非递归实现：

• 借助队列，对二叉树进行层次遍历；
• 在层次遍历的过程中，每次当队列中某一层的节点出队完成后，高度 + 1；
• 关键点：判别队列中某一层节点出队完成的标准是什么？
  在出队之前，此时队列中记录的只有某一层节点，所以队列的大小就是某一层节点的个数。当此个数减到 0 的时候，则说明该层节点全部出队完成

4.平衡二叉树

【题目】

输入一棵二叉树，判断该二叉树是否是平衡二叉树。

【代码】

	/**
     *
     * 输入一棵二叉树，求该树的深度。
     * 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，
     * 最长路径的长度为树的深度。
     * */
    public int TreeDepth(TreeNode root) {
        if (root == null) return 0;

        int left,right,high;

        left = TreeDepth(root.left);
        right = TreeDepth(root.right);

        high = left > right ? left : right;

        return high + 1;
    }

    /**
     * 平衡二叉树：
     * 1.空树或者左右子树高度差不超过1
     * 2.左右子树也是平衡二叉树
     * */
    public boolean IsBalanced_Solution(TreeNode root) {
        if (root == null) return true;

        int left,right,minus;

        left = TreeDepth(root.left);
        right = TreeDepth(root.right);
        minus = left - right;

        if (minus<=1 && minus>=-1) {
            return IsBalanced_Solution(root.left)
                    && IsBalanced_Solution(root.right);
        } else {
            return false;
        }
    }

5.二叉树的下一个结点

【题目】

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

【代码】

    /**
     * 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
     * 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
     *
     * 方法1：
     * 根据给定的节点，找到该二叉树的根节点
     * 在根据根节点进行中序遍历，然后获取下一个节点
     * */
    ArrayList<TreeLinkNode> path;
    public TreeLinkNode GetNext(TreeLinkNode pNode) {

        if (pNode == null) return null;

        TreeLinkNode root,res;

        root = pNode;
        while (root.next != null) {
            root = root.next;
        }
        path = new ArrayList<>();
        FindPath(root);

        int tar,i;
        tar = pNode.val;
        res = null;
        for (i=0; i<path.size(); i++) {
            if (path.get(i).val == tar) {
                if ((i+1) < path.size()) {
                    res = path.get(i+1);
                }
                break;
            }
        }
        return res;
    }

    public void FindPath(TreeLinkNode root) {
        if (root == null) return;

        if (root.left == null && root.right == null) {
            path.add(root);
            return;
        }

        FindPath(root.left);
        path.add(root);
        FindPath(root.right);
    }

【思考】

上面的是不需要考虑各种特殊情况的解法

仔细观察，可以把中序下一结点归为几种类型：

• 有右子树，下一结点是右子树中的最左结点，例如 B，下一结点是 H

• 无右子树，且结点是该结点父结点的左子树，则下一结点是该结点的父结点，例如 H，下一结点是 E

• 无右子树，且结点是该结点父结点的右子树，则我们一直沿着父结点追朔，直到找到某个结点是其父结点的左子树，如果存在这样的结点，那么这个结点的父结点就是我们要找的下一结点。例如 I，下一结点是 A；例如 G，并没有符合情况的结点，所以 G 没有下一结点