LeetCode - Medium - 814. Binary Tree Pruning-蒲公英云

LeetCode - Medium - 814. Binary Tree Pruning

Topic

Tree

Description

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:

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:

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

Example 3:

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));
    }
}