LeetCode의 Tree 100위

1.Symmetric Tree

두 갈래 트리를 지정하여 자신의 거울인지 확인합니다. 즉, 그 중심을 중심으로 대칭적입니다.
예를 들어 이 두 갈래 나무[1,2,2,3,4,4,3]는 대칭적이다.

   1    
 /   \   
2    2      
/ \   / \   
3  4   4  3

그러나 다음[1,2,2,null,3,null,3]은 아니다.

        1
       / \
      2   2
       \   \
        3    3 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
	//// 
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root,root);
    }
    
    public static boolean isMirror(TreeNode p,TreeNode q){
        if(p==null&&q==null) return true;
        if(p==null||q==null) return false;
        return (p.val==q.val)&&isMirror(p.left,q.right)&&isMirror(p.right,q.left);
    }
}

public boolean isSymmetric(TreeNode root) {
//// 
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    q.add(root);
    while (!q.isEmpty()) {
        TreeNode t1 = q.poll();
        TreeNode t2 = q.poll();
        if (t1 == null && t2 == null) continue;
        if (t1 == null || t2 == null) return false;
        if (t1.val != t2.val) return false;
        q.add(t1.left);
        q.add(t2.right);
        q.add(t1.right);
        q.add(t2.left);
    }
    return true;
}

2.Subtree of Another Tree

한 그루의 나무가 다른 나무의 자목인지 아닌지를 판독하다

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
 
public class Solution {
	/// 
    public boolean isSubtree(TreeNode s, TreeNode t) {
        return traverse(s,t);
    }
    public boolean equals(TreeNode x,TreeNode y)
    {
        if(x==null && y==null)
            return true;
        if(x==null || y==null)
            return false;
        return x.val==y.val && equals(x.left,y.left) && equals(x.right,y.right);
    }
    public boolean traverse(TreeNode s,TreeNode t)
    {
        return  s!=null && ( equals(s,t) || traverse(s.left,t) || traverse(s.right,t));
    }
}

3.Same Tree

두 나무가 동일한지 판단하기 Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null) return true;
        if(p==null||q==null) return false;
        if(p.val==q.val){
            return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
        }
        return false;
    }
}

4.Merge Two Binary Trees

두 나무를 결합하여 두 나무의 노드를 결합합니다. Example 1:

Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
       
        if(t2==null) return t1;
        if(t1==null) return t2;
        
        t1.val=t1.val+t2.val;

        t1.left= mergeTrees(t1.left,t2.left);
        t1.right= mergeTrees(t1.right,t2.right);
        return t1;
    }
}

5.Maximum Depth of Binary Tree

두 갈래 나무의 깊이 구하기 Example:
Given binary tree [3,9,20,null,null,15,7],

   3
   / \
  9  20
    /  \
   15   7

return its depth = 3.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }else{
            int left_height=maxDepth(root.left);
            int right_height=maxDepth(root.right);
            return java.lang.Math.max(left_height,right_height)+1;
        }
        
    }
}

6.Invert Binary Tree

두 갈래 트리 반전 예:

Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9
Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
   public TreeNode invertTree(TreeNode root) {
       if(root==null){
           return null;
       }
       TreeNode left=invertTree(root.left);
       TreeNode right=invertTree(root.right);
       root.left=right;
       root.right=left;
       return root;
       
   }
}