두 갈래 트리 테마: 거울 뒤집기, 대칭, 훑어보기, 모든 경로

     class TreeNode {       // 
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
     }
     public TreeNode invertTree(TreeNode root) {        // 
        if (root==null) return null;
        //if (root.left==null &&root.right==null) return null;
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
    public TreeNode invertTree2(TreeNode root) {        // 
        if (root==null) return null;
        Queue queue=new ArrayDeque<>();
        queue.add(root);
        while (queue.size()!=0){
            TreeNode treeNode=queue.remove();
            TreeNode temp=treeNode.left;
            treeNode.left=treeNode.right;
            treeNode.right=temp;
            if (treeNode.left!=null) queue.add(treeNode.left);
            if (treeNode.right!=null) queue.add(treeNode.right);
        }
        return root;
    }

class Solution {
   public boolean isSymmetric(TreeNode root) {  // 
        if (root==null) return true;
        return compare(root.left,root.right);
    }
    private boolean compare(TreeNode left,TreeNode right){
        if (left==null&&right==null) return true; // 
        else if (left==null || right==null) return false; // 
        else if (right.val!=left.val) return false;    // 
        else return compare(left.left,right.right)&&compare(left.right,right.left);   //       
    }
}

class Solution {
    List list= new ArrayList<>();
    public List binaryTreePaths(TreeNode root) { // 
            if (root!=null) temp(root,new String());
            return list;
    }
    private void temp(TreeNode root,String s){   // StringBuilder ， 
        if(root.right==null &&root.left==null){
            list.add(s+root.val);
            return ;
        }
        if (root.left!=null)temp(root.left,s+root.val+"->");
        if (root.right!=null)temp(root.right,s+root.val+"->");
    }
}

class Solution {
    public List preorderTraversal(TreeNode root) { // ，        --  
        List list= new ArrayList<>();
        if (root==null) return list;
        Deque queue =new ArrayDeque<>();
        queue.push(root);
        while (queue.size()>0){ // queue.size()>0  
            TreeNode node=queue.pop();
            list.add(node.val);
            if (node.right!=null)queue.push(node.right);
            if (node.left!=null)queue.push(node.left);
        }
        return list;
    }
}
/////////// //////////
class Solution {
    List list1= new ArrayList<>();
    public List preorderTraversal(TreeNode root) {
        if (root!=null) temp1(root);
        return list1;
    }
    private void temp1(TreeNode root){
        if (root==null) return;
        list1.add(root.val);
        temp1(root.left);
        temp1(root.right);
    }
}