Skip to content
qpzm7903 edited this page Aug 17, 2018 · 1 revision

814 Binary Tree Pruning

一个效率很低的代码

public class P814 {
    public TreeNode pruneTree(TreeNode root) {
        if(root.val == 0  && root.left == null && root.right == null) return null;
        inOrder(root);
        return root;
    }
    public void inOrder(TreeNode root) {
        if (root != null) {
            if(root.left != null)inOrder(root.left);
            checkAndDelete(root);
            if(root.right != null)inOrder(root.right);
            checkAndDelete(root);
        }
    }

    public void checkAndDelete(TreeNode root) {
        if (root.left != null) {
            if (root.left.val == 0 && root.left.left == null && root.left.right == null) {
                root.left = null;
            }
        }
        if (root.right != null) {
            if (root.right.val == 0 && root.right.left == null && root.right.right == null) {
                root.right = null;
            }
        }
    }
}

参考一下别人效率高的,思路也不难。

 public TreeNode pruneTree(TreeNode root) {
     TreeNode result = recursion(root);
     if(root.val == 0 && root.left == null && root.right == null)
         return null;
     return result;
     
 }
    public TreeNode recursion(TreeNode root){
        if(root == null)
            return null;
        TreeNode left = recursion(root.left);
        if(left == null)
            root.left = null;
        TreeNode right = recursion(root.right);
        if(right == null)
            root.right = null;
        if(root.val == 0 && root.left == null && root.right == null)
            return null;
        return root;
    }

还有更简单的方法,好强啊

 public TreeNode pruneTree(TreeNode root) {
    if(root == null) return null;
     root.left = pruneTree(root.left);
     root.right = pruneTree(root.right);
     if(root.val ==0 && root.left == null && root.right == null) return null;
     return root;
     
 }
Clone this wiki locally