Google – Binary Tree And

Google – Binary Tree And
一道非常有意思的题目！给两个Binary tree, leaves要么是0要么是1，中间结点无关紧要，用*或者其他什么符号表示就好了。现在要对两个binary tree做AND操作。要遵循以下几个rules:
1. 如果两个结点都是 *，and后也是 *
2. 如果其中一个结点是0，and后也是0
3. 如果其中一个结点是1，and后是另一个结点以及它的subtree

  public TreeNode treeAnd(TreeNode t1, TreeNode t2) {

    if (isLeaf(t1) || isLeaf(t2)) {

      if (t1.val == 0 || t2.val == 0) {

        return new TreeNode(0);

      }

      else if (t1.val == 1) {

        return t2;

      }

      else {

        return t1;

      }

    }

     

    TreeNode root = new TreeNode(-1);

    root.left = treeAnd(t1.left, t2.left);

    root.right = treeAnd(t1.right, t2.right);

    if (root.left.val == 0 && root.right.val == 0) {

      root.val = 0;

      root.left = null;

      root.right = null;

    }

     

    return root;

  }

   

  private boolean isLeaf(TreeNode root) {

    return root != null && root.left == null && root.right == null;

  }

Read full article from Google – Binary Tree And