算法问题——树相关问题

897. 递增顺序查找树

/**
 * Copyright (C), 2018-2020
 * FileName: increasingBST897
 * Author:   xjl
 * Date:     2020/8/21 14:01
 * Description: zhognxubianli
 */
package Tree;

import java.util.ArrayList;
import java.util.List;

public class increasingBST897 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public TreeNode increasingBST(TreeNode root) {
        List list = new ArrayList();
        inorder(root, list);
        /**
         * 重新建立二叉树
         */
        TreeNode ans = new TreeNode(list.get(0)), cur = ans;
        for (int i = 1; i < list.size(); i++) {
            cur.right = new TreeNode(list.get(i));
            cur = cur.right;
        }
        return ans;
    }

    /**
     * 中序遍历
     *
     * @param node
     * @param list
     */
    public void inorder(TreeNode node, List list) {
        if (node == null) return;
        inorder(node.left, list);
        list.add(node.val);
        inorder(node.right, list);
    }
}

617. 合并二叉树

/**
 * Copyright (C), 2018-2020
 * FileName: mergeTrees617
 * Author:   xjl
 * Date:     2020/8/21 13:46
 * Description: 合并二叉树
 */
package Tree;

public class mergeTrees617 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /**
     * 合并两个二叉树
     *
     * @param t1
     * @param t2
     * @return
     */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) return t2;
        if (t2 == null) return t1;
        t1.val += t2.val;
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }

}

872. 叶子相似的树

/**
 * Copyright (C), 2018-2020
 * FileName: leafSimilar872
 * Author:   xjl
 * Date:     2020/8/21 14:11
 * Description:
 */
package Tree;

import java.util.ArrayList;
import java.util.List;

public class leafSimilar872 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List list1 = slove(root1, new ArrayList());
        List list2 = slove(root2, new ArrayList());
        for (int i = 0; i < list1.size(); i++) {
            if (list1.get(i) != list2.get(i)) {
                return false;
            }
        }
        return true;
    }

    private List slove(TreeNode root, List list) {
        if (root.left != null) {
            slove(root.left, list);
        }
        if (root.right != null) {
            slove(root.right, list);
        }
        if (root.left == null && root.right == null) {
            list.add(root.val);
        }
        return list;
    }
    public boolean leafSimilar1(TreeNode root1, TreeNode root2) {
        List list1=new ArrayList();
        List list2=new ArrayList();
        preRootTraverse(root1,list1);
        preRootTraverse(root2,list2);
        return list1.equals(list2);
    }

    public void preRootTraverse(TreeNode root,List list){
        if(root!=null){
            if(root.left==null&&root.right==null){
                list.add(root.val);
            }
            preRootTraverse(root.left,list);
            preRootTraverse(root.right,list);
        }
    }
}

面试题 04.10. 检查子树

/**
 * Copyright (C), 2018-2020
 * FileName: isSubtree572
 * Author:   xjl
 * Date:     2020/8/21 9:46
 * Description: 子树
 */
package Tree;

public class isSubtree572 {
    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;
        }
    }

    public boolean isSubtree(TreeNode A, TreeNode B) {
        if (A == null && B == null) return true;
        if (A == null || B == null) return false;
        return slove(A, B) || isSubtree(A.left, B) || isSubtree(A.right, B);
    }

    private boolean slove(TreeNode s, TreeNode t) {
        if (t == null && s == null)
            return true;
        else if (t == null || s == null)
            return false;
        else if (t.val == s.val)
            return slove(s.left, t.left) && slove(s.right, t.right);
        else
            return false;
    }

    public boolean isSubtree1(TreeNode s, TreeNode t) {
        if (t == null) return true;   // t 为 null 一定都是 true
        if (s == null) return false;
        return isSubtree(s.left, t) || isSubtree(s.right, t) || isSameTree(s,t);
    }


    public boolean isSameTree(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 isSameTree(s.left, t.left) && isSameTree(s.right, t.right);
    }
}

655. 输出二叉树

/**
 * Copyright (C), 2018-2020
 * FileName: printTree655
 * Author:   xjl
 * Date:     2020/8/21 15:03
 * Description: 二叉树的打印
 */
package Tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class printTree655 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public List printTree(TreeNode root) {
        //获取树的高度
        int height = getHeight(root);
        //设置一个矩阵
        String[][] res = new String[height][(1