【算法题型总结】--4、树

public class Solution {
    /**
     * 
     * @param t1 TreeNode类 
     * @param t2 TreeNode类 
     * @return TreeNode类
     */
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return null;
        if (t1 == null || t2 == null) return t1 == null ? t2 : t1;
        // 此时 t1、t2 均不为 null
        // 合并节点的值
        t1.val = t1.val + t2.val;
        // 合并左子树
        t1.left = mergeTrees(t1.left, t2.left);
        // 合并右子树
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
}

public class Solution {
    // 中序遍历的递归写法 思路清晰但是不够高效
    ArrayList<Integer> list = new ArrayList<>();
    public int[] inorderTraversal (TreeNode root) {
        recur(root);
        return list.stream().mapToInt(Integer::valueOf).toArray();
    }
    public void recur(TreeNode root) {
        if (root == null) return;
        recur(root.left);
        list.add(root.val);
        recur(root.right);
    }
}

public int[] inorderTraversal (TreeNode root) {
        ArrayList<Integer> arrList=new ArrayList<>();
        Stack<TreeNode> stack=new Stack<>();
        while(root!=null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
                root=stack.pop();
                arrList.add(root.val);
                root=root.right;
        }
        return arrList.stream().mapToInt(Integer::valueOf).toArray();
    }

public TreeNode Mirror (TreeNode pRoot) {
        if(pRoot == null) {
            return null;
        }
        if(pRoot.left == null && pRoot.right == null) {
            return pRoot;
        }
        TreeNode L = Mirror(pRoot.left);
        TreeNode R = Mirror(pRoot.right);
        pRoot.left = R;
        pRoot.right = L;
        return pRoot;
    }

public int maxDepth (TreeNode root) {
        //通过层次遍历计算二叉树的深度
        if(root==null) return 0;
        Queue<TreeNode>queue=new LinkedList<>();
        queue.offer(root);
        int level=0,size;
        while(!queue.isEmpty()){
            size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode node=queue.poll();
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
            }
            level++;
        }
        return level;
    }

import java.util.*; 
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */
public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int maxDepth (TreeNode root) {
        if(root==null){
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
         
        return 1 + Math.max(left,right);
    }
}

HashMap<Integer,Integer> inOrderHashMap = new HashMap<>();
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        if (xianxu==null||zhongxu==null||xianxu.length==0||zhongxu.length==0) return new int[0];
        for (int i = 0; i < zhongxu.length; i++) {
            inOrderHashMap.put(zhongxu[i],i);
        }
        TreeNode root = buildTree(xianxu, 0, xianxu.length - 1, inOrderHashMap, 0, zhongxu.length - 1);
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int[] res = new int[xianxu.length];
        int count =0;
        while (!queue.isEmpty()){
            //拿到当前层元素个数
            int len = queue.size();
            System.out.println(len);
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                if (node.left!=null) queue.offer(node.left);
                if (node.right!=null) queue.offer(node.right);
                //到最后一个元素了
                if (i==len-1) res[count++] = node.val;
            }
        }
        //count是有效数组元素 0下标开始 跟左闭右开刚好对冲
        return Arrays.copyOfRange(res,0,count);
    }
    //inOrder: [inLeft,rootIndex-1] rootIndex [rootIndex+1,inRight]
    //preOrder: preLeft [preLeft+1,preLeft+rootIndex-inLeft] [preLeft+rootIndex-inLeft+1,preRight]
    private TreeNode buildTree(int[] xianxu, int preLeft, int preRight, HashMap<Integer, Integer> inOrderHashMap, int inLeft, int inRight) {
        //preLeft == preRight时 也要执行的 --叶子节点罢了
        if (preLeft>preRight||inLeft>inRight) return null;
        int rootIndex = inOrderHashMap.get(xianxu[preLeft]);
        TreeNode root = new TreeNode(xianxu[preLeft]);
        root.left = buildTree(xianxu, preLeft + 1, preLeft + rootIndex - inLeft, inOrderHashMap, inLeft, rootIndex - 1);
        root.right = buildTree(xianxu,preLeft+rootIndex-inLeft+1,preRight,inOrderHashMap,rootIndex+1,inRight);
        return root;
    }

  public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        if(root.val == o1 || root.val == o2){
            return root.val;
        }
        TreeNode treeNode = order(root, o1, o2);
        return treeNode.val;
    }
    public TreeNode order(TreeNode root, int o1, int o2){
        if(root == null)
            return null;
        if(root.val == o1 || root.val == o2)
            return root;
        TreeNode left = order(root.left, o1, o2);
        TreeNode right = order(root.right, o1, o2);
         
        if(left != null && right != null)
            return root;
        if(left == null && right == null)
            return null;
         
        return left == null? right: left;
    }