814. 二叉树剪枝

痛定思痛。 2023-10-05 21:10 243阅读 0赞

给定二叉树根结点 `root` ，此外树的每个结点的值要么是 0，要么是 1。

返回移除了所有不包含 1 的子树的原二叉树。

( 节点 X 的子树为 X 本身，以及所有 X 的后代。)

示例1:
    输入: [1,null,0,0,1]
    输出: [1,null,0,null,1]
     
    解释: 
    只有红色节点满足条件“所有不包含 1 的子树”。
    右图为返回的答案。

示例2:
    输入: [1,0,1,0,0,0,1]
    输出: [1,null,1,null,1]

示例3:
    输入: [1,1,0,1,1,0,1,0]
    输出: [1,1,0,1,1,null,1]

**说明:**

*  给定的二叉树最多有 `100` 个节点。
 *  每个节点的值只会为 `0` 或 `1` 。

package Solution814;
    
    class Solution {
    	public TreeNode pruneTree(TreeNode root) {
    		if (root == null) {
    			return null;
    		}
    
    		root.left = pruneTree(root.left);
    		root.right = pruneTree(root.right);
    
    		if (root.left == null && root.right == null && root.val == 0) {
    			return null;
    		}
    
    		return root;
    
    	}
    
    	static void inorder(TreeNode node) {
    		if (node == null)
    			return;
    
    		/* first recur on left child */
    		inorder(node.left);
    
    		/* then print the data of node */
    		System.out.printf("%d ", node.val);
    
    		/* now recur on right child */
    		inorder(node.right);
    	}
    
    	public static void main(String[] args) {
    
    		Solution sol = new Solution();
    
    		// Add nodes to the binary tree
    		TreeNode root = new TreeNode(1);
    		// root.left = new TreeNode(2);
    		root.right = new TreeNode(0);
    		root.right.left = new TreeNode(0);
    		root.right.right = new TreeNode(1);
    		inorder(root);
    		sol.pruneTree(root);
    		System.out.println();
    		inorder(root);
    
    	}
    }