두 갈래 나무(2)

두 갈래 나무의 두 결점의 최대 공통 부모 노드를 구하다

​ 1
/2 3//4 5 6 7////위 그림에서 보듯이 정수 1, 2, 3,...무한히 큰 두 갈래 나무를 이루었다.어떤 결점에서 루트 결점(번호 1의 결점)까지는 유일한 경로가 있다. 예를 들어 5에서 루트 결점까지의 경로는 (5, 2, 1)이고, 4에서 루트 결점까지의 경로는 (4, 2, 1)이며, 루트 결점 1에서 루트 결점까지의 경로에는 하나의 결점 1만 포함되기 때문에 경로는 (1)이다.두 결점 x와 y에 대해 그들이 뿌리 결점까지의 경로가 각각 (x1,x2,..., 1)과 (y1,y2,..., 1)이라고 가정하면 반드시 두 개의 정수 i와 j가 존재하기 때문에 xi와 yj부터 시작하여 xi=yj,xi+1=yj+1,xi+2=yj+2,...현재의 문제는 x와 y를 정하고 그들의 공공 부모 노드, 즉 xi(즉 yj)를 요구하는 것이다.

예제

입력

10 4  // ， x y（1≤x, y≤2^31-1）。

출력

2  // ， xi， 。

Java

import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNext()) {
            int x=scanner.nextInt();
            int y=scanner.nextInt();

            while(x!=y) {
                if(x>y)
                    x=x/2;
                else
                    y=y/2;
            }
            System.out.println(x);
        }
    }
}
// https://blog.csdn.net/zd454909951/article/details/78855707

C++

#include 
#include 
#include 
using namespace std;

int main(){
//    freopen("a.txt", "r", stdin);
    int x, y;
    while(cin >> x >> y){
        // ， y
        while(x != y){
            if(x > y){
                x /= 2;
            }
            else{
                y /= 2;
            }
        }
        cout << x << endl;
    }
    return 0;
}
//https://blog.csdn.net/Void_worker/article/details/81123175

두 갈래 나무의 서열화

두 갈래 나무가 파일로 기록되는 과정을 두 갈래 나무의 서열화라고 한다.서열화하는 방법은 매우 많다. 여기서 우리는 괄호 서열의 방법으로 그것을 서열화한다. 이른바 괄호 서열은 한 노드에 대해 괄호를 생성하는 것을 가리킨다. 괄호 안은 그 하위 나무의 괄호 서열이다. 그 중에서 왼쪽 아들(존재하는 경우)의 괄호는 앞에 있고 오른쪽 아들(존재하는 경우)의 괄호는 뒤에 있다.주어진 트리에 대해 효율적인 알고리즘을 설계하여 서열화하십시오.
트리의 루트 노드 바늘 루트를 지정합니다. 서열화된 괄호 서열을 나타내는 문자열을 되돌려 주십시오.

C++

//https://www.nowcoder.com/questionTerminal/e3a3a1a956914d8ca5688ea47a5cf9c9

import java.util.*;
 
/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;
    public TreeNode(int val) {
        this.val = val;
    }
}*/
public class TreeToSequence {
    public String toSequence(TreeNode root) {
        // write code here
        String str="";ui,,0/'[-;;;0]'
            return "";
        }else{
            str="(";
            str+=toSequence(root.left);
            str+=toSequence(root.right);
            str+=")";
            return str;
        }
    }
}

Java

//https://www.nowcoder.com/questionTerminal/e3a3a1a956914d8ca5688ea47a5cf9c9

class TreeToSequence {
public:
    string getAns(TreeNode *root){
        string temp;
        if(!root) return temp;
        string s1,s2;
        if(root->left)
           s1 = getAns(root->left);
        if(root->right)
           s2 =getAns(root->right);
        temp+='(';
        temp+=s1;
        temp+=s2;
        temp+=')';
        return temp;
         
    }
    string toSequence(TreeNode* root) {
         string ans;
         if(!root) return ans;
         ans=getAns(root);
         return ans;
    }
};

두 갈래 나무 한 그루를 주어 이 나무의 중서로 되돌아가다
예:
주어진 두 갈래 나무는 {1,#,2,3},

   1↵    ↵     2↵    /↵   3↵

[1,3,2]로 돌아갑니다.
비고: 귀속적인 해법은 너무 새롭지 않다. 너는 교체적인 방법으로 이 문제를 풀 수 있니?
"{1,#,2,3}"의 의미를 잘 모르면 계속 읽어주세요
우리는 다음과 같은 방법으로 두 갈래 나무를 서열화한다.
두 갈래 나무의 서열화는 층층이 훑어보는 원칙에 따른다. # "이 위치는 하나의 경로의 종결이고 아래에 결점이 더 이상 존재하지 않는다는 것을 대표한다.
예:

   1↵  / ↵ 2   3↵    /↵   4↵    ↵     5

상술한 두 갈래 나무의 서열화 결과는'{1,2,3,#,#,4,#,#,5}'이다.

Java

//https://www.nowcoder.com/questionTerminal/1b25a41f25f241228abd7eb9b768ab9b

/*
*  
*/
    public ArrayList inorderTraversal(TreeNode root) {
        Stack stack = new Stack();
        ArrayList res = new ArrayList();
        TreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            res.add(node.val);
            node = node.right;
        }
        return res;
    }

C++

//https://www.nowcoder.com/questionTerminal/1b25a41f25f241228abd7eb9b768ab9b

class Solution {
public:
    vector inorderTraversal(TreeNode *root) {
        vector result;
        if(!root)
            return result;
        stack s;
        TreeNode *p=root;
        while(!s.empty() || p!=NULL)
        {
            while(p)
            {
                s.push(p);
                p=p->left;  
            }
            if(!s.empty())
            {
                p = s.top();
                s.pop();
                result.push_back(p->val);
                p = p->right;
            }
        }
        return result;
    }
};