LeetCode - Medium - 814. Binary Tree Pruning

我不是女神ヾ 2022-10-08 05:44 63阅读 0赞

## Topic ##

*  Tree

## Description ##

[https://leetcode.com/problems/binary-tree-pruning/][https_leetcode.com_problems_binary-tree-pruning]

Given the `root` of a binary tree, return the same tree where every subtree (of the given tree) not containing a `1` has been removed.

A subtree of a node `node` is `node` plus every node that is a descendant of `node`.

**Example 1:**  
![0a21aaf7128ba5a691f0bc88b6b24c76.png][]

Input: root = [1,null,0,0,1]
    Output: [1,null,0,null,1]
    Explanation: 
    Only the red nodes satisfy the property "every subtree not containing a 1".
    The diagram on the right represents the answer.

**Example 2:**  
![8918491bf7da9b086b5e5439744dfb36.png][]

Input: root = [1,0,1,0,0,0,1]
    Output: [1,null,1,null,1]

**Example 3:**

![3ecc2b4a71a5cd519a7e668ddd7a7f73.png][]

Input: root = [1,1,0,1,1,0,1,0]
    Output: [1,1,0,1,1,null,1]

**Constraints:**

*  The number of nodes in the tree is in the range `[1, 200]`.
 *  `Node.val` is either `0` or `1`.

## Analysis ##

从树底的叶子节点开始由下往上，把不符合题意得节点剔除，因此用到二叉树的后序遍历模式。

方法一：二叉树的后序遍历模式的递归版。

方法二：二叉树的后序遍历模式的迭代版。

## Submission ##

import java.util.LinkedList;
    
    import com.lun.util.BinaryTree.TreeNode;
    
    public class BinaryTreePruning { 
    	
    	//方法一：用到后序遍历模式的递归版
        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;
        }
        
        //方法二：用到后序遍历模式的迭代版
        public TreeNode pruneTree2(TreeNode root) { 
        	if(root == null) return null;
        	
        	LinkedList<TreeNode[]> stack = new LinkedList<>();//需要将节点以及其父节点存入同一栈帧。
        	TreeNode fakeRoot = new TreeNode(-1, root, null);//对于根节点没有父节点的情况，可以给它弄个临时父节点。临时父节点的左节点指向根节点
        	TreeNode p = root, lastNodeVisited = null, parent = fakeRoot;
        	
        	while(!stack.isEmpty() || p != null) { 
        		
        		if(p != null) { 
        			stack.push(new TreeNode[] { parent, p});
        			parent = p;
        			p = p.left;
        		}else { 
        			TreeNode[] peekOne = stack.peek();
        			if(peekOne[1].right != null && peekOne[1].right != lastNodeVisited) { 
        				parent = peekOne[1];
        				p = peekOne[1].right;
        			}else { 
        				if(peekOne[1].val == 0 && peekOne[1].left == null && peekOne[1].right == null) { 
        					if(peekOne[0].left == peekOne[1]) { 
        						peekOne[0].left = null;
        					}else { 
        						peekOne[0].right = null;
        					}
        				}
        				lastNodeVisited = stack.pop()[1];
        			}
        		}
        	}
        	
        	return fakeRoot.left;
        }
    
    }

## Test ##

public class BinaryTreePruningTest { 
    
    	@Test
    	public void test() { 
    		BinaryTreePruning obj = new BinaryTreePruning();
    
    		TreeNode original1 = BinaryTree.integers2BinaryTree(1,null,0,0,1);
    		TreeNode expected1 = BinaryTree.integers2BinaryTree(1,null,0,null,1);
    		assertTrue(BinaryTree.equals(obj.pruneTree(original1), expected1));
    
    		TreeNode original2 = BinaryTree.integers2BinaryTree(1,0,1,0,0,0,1);
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(1,null,1,null,1);
    		assertTrue(BinaryTree.equals(obj.pruneTree(original2), expected2));
    		
    		TreeNode original3 = BinaryTree.integers2BinaryTree(1,1,0,1,1,0,1,0);
    		TreeNode expected3 = BinaryTree.integers2BinaryTree(1,1,0,1,1,null,1);
    		assertTrue(BinaryTree.equals(obj.pruneTree(original3), expected3));
    	}
    	
    	@Test
    	public void test2() { 
    		BinaryTreePruning obj = new BinaryTreePruning();
    		
    		TreeNode original1 = BinaryTree.integers2BinaryTree(1,null,0,0,1);
    		TreeNode expected1 = BinaryTree.integers2BinaryTree(1,null,0,null,1);
    		assertTrue(BinaryTree.equals(obj.pruneTree2(original1), expected1));
    		
    		TreeNode original2 = BinaryTree.integers2BinaryTree(1,0,1,0,0,0,1);
    		TreeNode expected2 = BinaryTree.integers2BinaryTree(1,null,1,null,1);
    		assertTrue(BinaryTree.equals(obj.pruneTree2(original2), expected2));
    		
    		TreeNode original3 = BinaryTree.integers2BinaryTree(1,1,0,1,1,0,1,0);
    		TreeNode expected3 = BinaryTree.integers2BinaryTree(1,1,0,1,1,null,1);
    		assertTrue(BinaryTree.equals(obj.pruneTree2(original3), expected3));
    	}
    }

[https_leetcode.com_problems_binary-tree-pruning]: https://leetcode.com/problems/binary-tree-pruning/
[0a21aaf7128ba5a691f0bc88b6b24c76.png]: /images/20221005/af06d8bd1cb04ff7a57fbf9bb793abe2.png
[8918491bf7da9b086b5e5439744dfb36.png]: /images/20221005/82b05ed571aa42ce8773089c1ed7c892.png
[3ecc2b4a71a5cd519a7e668ddd7a7f73.png]: /images/20221005/72a352e137d545caab08ac753037d9a1.png