두 갈래 나무 - 중차적 역류와 후차적 역류 나무 구조 두 갈래 나무 - 중등

2030 단어 LintCode

묘사


중차 역류와 후차 역류 트리에 따라 두 갈래 트리를 구성한다
너는 트리에 같은 수치의 노드가 존재하지 않는다고 가정할 수 있다
당신은 실제 면접에서 이 문제를 만난 적이 있습니까?예.

예제


나무의 중서 역행을 제시한다:[1,2,3]과 후서 역행:[1,3,2]
다음 트리로 돌아갑니다.
  2
 / \
1    3

제목 링크


프로그램

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param inorder: A list of integers that inorder traversal of a tree
     * @param postorder: A list of integers that postorder traversal of a tree
     * @return: Root of a tree
     */
    TreeNode * buildTree(vector &inorder, vector &postorder) {
        // write your code here
        TreeNode * root = NULL;
        vector l_postorder, r_postorder, l_inorder, r_inorder;
        int i, root_index = 0;
        if(postorder.empty() != 1 || inorder.empty() != 1){
            //   
            root = new TreeNode(postorder[postorder.size() - 1]);
            //   
            for(i = 0; i < inorder.size(); i++){
                if(postorder[postorder.size() - 1] == inorder[i])
                    break;
                root_index++;
            }
            //   、 
            for(i = 0; i < root_index; i++){
                l_inorder.push_back(inorder[i]);
                l_postorder.push_back(postorder[i]);
            }
            for(i = root_index + 1; i < inorder.size(); i++){
                r_inorder.push_back(inorder[i]);
                r_postorder.push_back(postorder[i-1]);
            }
            
            root->left = buildTree(l_inorder, l_postorder);
            root->right = buildTree(r_inorder, r_postorder);
        }
        return root;
    }
};

좋은 웹페이지 즐겨찾기