【先序遍历】
给定一个有 N 个节点的二叉树，每个节点都有一个不同于其他节点且处于 {1, ..., N} 中的值。
通过交换节点的左子节点和右子节点，可以翻转该二叉树中的节点。
考虑从根节点开始的先序遍历报告的 N 值序列。将这一 N 值序列称为树的行程。
（回想一下，节点的先序遍历意味着我们报告当前节点的值，然后先序遍历左子节点，再先序遍历右子节点。）
我们的目标是翻转最少的树中节点，以便树的行程与给定的行程 voyage 相匹配。
如果可以，则返回翻转的所有节点的值的列表。你可以按任何顺序返回答案。
如果不能，则返回列表 [-1]。
Solutions
1
2
3
4
5
6
7
|
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
|
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
|
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
树的题有不少都是在遍历到的时候进行操作。