折纸、寻找错误结点

╰+哭是因爲堅強的太久メ 2022-06-09 09:53 144阅读 0赞

请把纸条竖着放在桌⼦上，然后从纸条的下边向上⽅对折，压出折痕后再展 开。此时有1条折痕，突起的⽅向指向纸条的背⾯，这条折痕叫做“下”折痕 ；突起的⽅向指向纸条正⾯的折痕叫做“上”折痕。如果每次都从下边向上⽅ 对折，对折N次。请从上到下计算出所有折痕的⽅向。

给定折的次数n,请返回从上到下的折痕的数组，若为下折痕则对应元素为”down”,若为上折痕则为”up”.

#测试样例：
    1
    #返回：["down"]

**我的提交**

# -*- coding:utf-8 -*-
    
    class FoldPaper:
        def foldPaper(self, n):
            # write code here
            if n < 1:
                return []
            if n == 1:
                return ['down']
            queue = ['down']
            for i in range(n - 1):
                temp = []
                while queue:
                    temp.append('down')
                    temp.append(queue.pop(0))
                    temp.append('up')
                    if queue:
                        temp.append(queue.pop(0))
                queue = temp
            return queue

**参考答案**

class FoldPaper {
    public:
        void fold(int i,int N,bool down,vector &ret){
            if(i > N) return;
            fold(i + 1,N,true,ret);
            ret.push_back(down ? "down" : "up");
            fold(i + 1,N,false,ret);
        }
        vector foldPaper(int n) {
            vector ret;
            fold(1,n,true,ret);
            return ret;
        }
    };

--------------------

### 寻找错误结点 ###

一棵二叉树原本是搜索二叉树，但是其中有两个节点调换了位置，使得这棵二叉树不再是搜索二叉树，请找到这两个错误节点并返回他们的值。保证二叉树中结点的值各不相同。

给定一棵树的根结点，请返回两个调换了位置的值，其中小的值在前

**参考答案**  
python

# -*- coding:utf-8 -*-
    
    # class TreeNode:
    # def __init__(self, x):
    # self.val = x
    # self.left = None
    # self.right = None
    class FindErrorNode:
        def findError(self, root):
            # write code here
            if not root:
                return None
            stack = []
            head, pre = root, None
            errNum = [0, 0]
            res = []
            while len(stack) or head:
                if head:
                    stack.append(head)
                    head = head.left
                else:
                    cur = stack.pop()
                    if pre and pre.val > cur.val:
                        if errNum[0] == 0:
                            errNum[0] = pre.val
                        else:
                            errNum[0] = errNum[0]
                        errNum[1] = cur.val
                    pre = cur
                    head = cur.right
            res = errNum[::-1]
            return res

java

/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/
    
    class FindErrorNode {
    public:
        void get(TreeNode* rt,vector &mid){
            if(rt->left) get(rt->left,mid);
            mid.push_back(rt->val);
            if(rt->right) get(rt->right,mid);
        }
        vector findError(TreeNode* root) {
            vector mid;
            get(root,mid);
            int A = -1,B = -1;
            for(int i = 1,lim = mid.size();i < lim;++ i)
            if(mid[i] < mid[i - 1])
                A = A == -1 ? mid[i - 1] : A,B = mid[i];
            vector ret;
            ret.push_back(B); ret.push_back(A);
            return ret;
        }
    };