ProblemSet of Tree Algorithms

树算法尽量用递归来做。

LeetCode

951. Flip Equivalent Binary Trees
算法一：

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

算法二：树的最小表示

class Solution {
    public boolean flipEquiv(TreeNode root1, TreeNode root2) {
        
        ArrayList<Integer> arr1=new ArrayList<>();
        ArrayList<Integer> arr2=new ArrayList<>();
        dfs(root1,arr1);
        dfs(root2,arr2);
        if(arr1.size()!=arr2.size())
            return false;
        print(arr1);
        System.out.println();
        print(arr2);
        int i=0;
        for(;i<arr1.size();i++){
            if(arr1.get(i)!=arr2.get(i))
                break;
        }
        return i==arr1.size();
    }
    
    public void dfs(TreeNode node,ArrayList<Integer> arr){
        if(node==null)
            return;
        arr.add(node.val);
        int l=node.left==null?-1:node.left.val;
        int r=node.right==null?-1:node.right.val;
        if(l<r){
            dfs(node.left,arr);
            dfs(node.right,arr);
        }
        else{
            dfs(node.right,arr);
            dfs(node.left,arr);
        }
    }
    
    public static void print(List<Integer> arr){
        for(int i:arr)
            System.out.print(i+" ");
    }
}

1038. Binary Search Tree to Greater Sum Tree
这个问题我用非递归解的。

class Solution {
    
    public static ArrayList<TreeNode> arr;
    public TreeNode bstToGst(TreeNode root) {
        
        
        arr=new ArrayList<>();
        inOrder(root);
        for(int i=arr.size()-2;i>=0;i--){
            arr.get(i).val+=arr.get(i+1).val;
        }
        
        return root;
    }
    
    public void inOrder(TreeNode node){
        if(node==null)
            return;
        inOrder(node.left);
        arr.add(node);
        inOrder(node.right);
    }
}

递归也很简单

class Solution {
    
    public static int sum;
    
    public TreeNode bstToGst(TreeNode root) {
        
        sum=0;
        postOrder(root);
        return root;
    }
    public static void postOrder(TreeNode node){
        
        if(node==null)
            return;
        else{
            postOrder(node.right);
            sum+=node.val;
            node.val=sum;
            postOrder(node.left);
        }
    }
}

AcWing

157. 树形地铁系统
与1038. Binary Search Tree to Greater Sum Tree类似都是利用最小表示法来判断两棵树是否同构。

import java.util.Scanner;
import java.util.Collections;
import java.util.ArrayList;
class Main{
    
    public static int idx;
    
    public static String recursive(String s)
    {
        ArrayList<String> list=new ArrayList<>();
        idx++;
        while(s.charAt(idx)=='0')
            list.add(recursive(s));
        idx++;
        Collections.sort(list);
        StringBuilder res=new StringBuilder();
        res.append('0');
        for(String str:list)
            res.append(str);
        res.append('1');
        return res.toString();
    }
    
    
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        
        int T=sc.nextInt();

        while(T>0){
            String a="0"+sc.next()+"1";
            String b="0"+sc.next()+"1";
            idx=0;
            String a1=recursive(a);
            idx=0;
            String b1=recursive(b);
            if(a1.equals(b1))
                System.out.println("same");
            else
                System.out.println("different");
            T--;
        }
    }
}