You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

971. 翻转二叉树以匹配先序遍历 - Flip Binary Tree To Match Preorder Traversal

. 3 min read

【先序遍历】

给定一个有 N 个节点的二叉树,每个节点都有一个不同于其他节点且处于 {1, ..., N} 中的值。

通过交换节点的左子节点和右子节点,可以翻转该二叉树中的节点。

考虑从根节点开始的先序遍历报告的 N 值序列。将这一 N 值序列称为树的行程。

(回想一下,节点的先序遍历意味着我们报告当前节点的值,然后先序遍历左子节点,再先序遍历右子节点。)

我们的目标是翻转最少的树中节点,以便树的行程与给定的行程 voyage 相匹配。

如果可以,则返回翻转的所有节点的值的列表。你可以按任何顺序返回答案。

如果不能,则返回列表 [-1]。

Example:

示例 1:

img
输入:root = [1,2], voyage = [2,1]
输出:[-1]

示例 2:

img
输入:root = [1,2,3], voyage = [1,3,2]
输出:[1]

示例 3:

img
输入:root = [1,2,3], voyage = [1,2,3]
输出:[]

Solutions

Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;     
    TreeNode right;
    TreeNode(int x) { val = x; }
}

Solution 【先序遍历】 ( 8ms)

class Solution {
	List<Integer> result = new LinkedList<>();
	int i = 0;
	public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
		
		boolean res = preOrderTraverse(root, voyage);
		if(!res){
			result.clear();
			result.add(-1);
		}
		return result;
	}

	public boolean preOrderTraverse(TreeNode node, int[] voyage) {
		if (node == null)
			return true;
		if(node.val != voyage[i])
			return false;
		
		int left = 0;
		int right = 0;
		
		if(node.left != null) left = node.left.val;
		if(node.right != null) right = node.right.val;
		
		if(left != 0 && right != 0) {
			if(left != voyage[i+1]) { //尝试翻转
                result.add(node.val);
				TreeNode tmp = node.right;
				node.right = node.left;
				node.left = tmp;
			}
		}
		i++;
        boolean res_left = preOrderTraverse(node.left, voyage);
        boolean res_right = preOrderTraverse(node.right, voyage);
		return res_left && res_right;
	}
}

复杂度分析

Solution 【考点标签】 ( 5ms)

class Solution {
    int[] v;
    List<Integer> ret;
    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        ret=new ArrayList<Integer>();
        if(root==null)return ret;
        v=voyage;
        boolean re=real(root,0,voyage.length-1);
        if(!re)
        {
            ret.clear();
            ret.add(-1);
            return ret;
        }
        return ret;
    }
    boolean real(TreeNode root,int left,int right)
    {
        if(left>right||root.val!=v[left])return false;
        if(root.left==null&&root.right==null&&left!=right)return false;
        if(root.left==null&&root.right==null)return true;
        if(root.left==null&&root.right!=null)return real(root.right,left+1,right);
        if(root.left!=null&&root.right==null)return real(root.left,left+1,right);
        int tleft=0,tright=0;
        for(int i=left+1;i<=right;i++)
        {
            if(root.left.val==v[i])tleft=i;
            if(root.right.val==v[i])tright=i;
        }
        if(tleft>tright)
        {
            ret.add(root.val);
            return real(root.right,tright,tleft-1)&&real(root.left,tleft,right);
        }
        return real(root.left,tleft,tright-1)&&real(root.right,tright,right);
    }
}

Notes

树的题有不少都是在遍历到的时候进行操作。