三面算法题

贴一下三面题目写的代码，面试写的很笨蛋，还可以优化，但是没时间了，编辑：好像不是最优解

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello World!");
        // 自己写案例
        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(2);
        head.right = new TreeNode(3);
        head.left.left = new TreeNode(4);
        head.left.right = new TreeNode(5);
        head.right.left = new TreeNode(6);
        int ans = new Main().getLatestRightestNode(head).val;
        System.out.println(ans);
    }




    public TreeNode getLatestRightestNode(TreeNode head){
        Result result = get(new Result(head,0));
        return result.node;
    }


    public Result get(Result result){
        TreeNode head = result.node;
        int height = result.height;
        // 这里判断是可以优化的，左子树为空的情况可以合并，面试时没优化，把情况都写出来看的比较清除
        if (head.left==null&&head.right==null){
            return new Result(head,height);
        }
        // 左子树为空说明就是该节点
        if (head.left == null){
            return get(new Result(head,height));
        }
        if (head.right == null){
            return get(new Result(head.left,height+1));
        }
        // 递归调用，判断左子树与右子树的结果，取深度更深的
        Result left = get(new Result(head.left,height+1));
        //System.out.println(left.node.val);
        Result right = get(new Result(head.right,height+1));
        //System.out.println(right.node.val);
        if (right.height>=left.height){
            return right;
        }else{
            return left;
        }


    }


}
class Result{
  	//递归调用结果，需要记录深度，自己定义的
    TreeNode node;
    int height;
    Result(TreeNode node,int height){
        this.node = node;
        this.height = height;
    }
}




class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;


    TreeNode(){


    }


    TreeNode(int val){
        this.val = val;
        this.left = null;
        this.right = null;
    }




}