leetcode971. 翻转二叉树以匹配先序遍历

leetcode971. 翻转二叉树以匹配先序遍历

三月 14, 2020

leetcode971. 翻转二叉树以匹配先序遍历

这道题的说明还没有题目清晰,所以不粘题内容了.

思路

前序遍历,遇到当前节点和对应的voyage值不相等的时候,返回false.
并且看当前节点的左节点是不是满足下一个voyage,如果不满足要交换左右子树.

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 {
    public ArrayList<Integer> list=new ArrayList<>();
    public List<Integer> flipMatchVoyage(TreeNode root, int[] voyage) {
        if(root==null)return list;
        boolean f=traverse(root,voyage);
        if(!f){
            //false得返回-1
            list=new ArrayList<>();
            list.add(-1);
        }
        return list;
    }
    public int n=0;//n是节点的数量
    public boolean traverse(TreeNode root,int[] voyage){
        if(root==null){
            n--;//节点的数量-1
            if(n==voyage.length-1)
                return true;
            else return false;
        }
        if(root.val!=voyage[n])return false;//当前节点比较
        
        n++;
        
        if(root.left!=null){//右子树节点比较
            if(root.left.val!=voyage[n]){
                if(root.right!=null&&root.right.val==voyage[n]){
                    TreeNode tmp=root.left;
                    root.left=root.right;
                    root.right=tmp;
                    list.add(root.val);
                }
            }
        }
        boolean left=traverse(root.left,voyage);
        n++;
        boolean right=traverse(root.right,voyage);
        return left||right;//如果满足条件,左右子树会有一个返回true
    }
}

leetcode 55/100