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

【先序遍历】

Problem Link

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

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

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

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

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

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

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

Example:

示例 1:

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

示例 2:

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

示例 3:

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

Solutions

1
2
3
4
5
6
7
8
Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;     
    TreeNode right;
    TreeNode(int x) { val = x; }
}

Solution 【先序遍历】 ( 8ms)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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

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

updatedupdated2021-03-052021-03-05