[数据结构与算法]二叉树题目

判断二叉树是否对称

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return bool布尔型
     */
    public boolean isSymmetric (TreeNode root) {
        // write code here
        if(root == null){
            return true;
        }
        return func(root.left,root.right);
    }
    
    public boolean func(TreeNode leftTree,TreeNode rightTree){
        if(leftTree == null && rightTree == null){
            return true;
        }
        if(leftTree == null && rightTree != null){
            return false;
        }
        if(leftTree != null && rightTree == null){
            return false;
        }
        if(leftTree.val != rightTree.val){
            return false;
        }
        return func(leftTree.left,rightTree.right) && func(leftTree.right,rightTree.left);
    }
}

二叉树中是否存在节点和为指定值的路径

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root == null){
            return false;
        }
        sum = sum - root.val;
        if(sum == 0 && root.left == null && root.right == null){
            return true;
        }
        return hasPathSum(root.left,sum) || hasPathSum(root.right,sum);
    }
}

二叉树根节点到叶子节点的所有路径和

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    public int sumNumbers (TreeNode root) {
        // write code here
        if(root == null){
            return 0;
        }
        return numbers(root,0);
    }
    
    public int numbers(TreeNode root,int sum){
        if(root == null){
            return 0;
        }
        sum = sum * 10 + root.val;
        if(root.left == null && root.right == null){
            return sum;
        }
        return numbers(root.left,sum) + numbers(root.right,sum);
    }
}

在二叉树中找到两个节点的最近公共祖先

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        return ancestor(root,o1,o2).val;
    }
    
    public TreeNode ancestor(TreeNode root, int o1, int o2){
        if(root == null){
            return null;
        }
        if(root.val == o1 || root.val == o2){
            return root;
        }
        TreeNode node1 = ancestor(root.left,o1,o2);
        TreeNode node2 = ancestor(root.right,o1,o2);
        if(node1 == null){
            return node2;
        }
        if(node2 == null){
            return node1;
        }
        return root;
    }
}