二叉树

二叉树

二叉搜索树与双向链表

「栈实现中序遍历」

 Node* treeToDoublyList(Node* root) {
     if(root==NULL)return NULL;
     stack<Node*>s;
      Node*head=root,*pre=NULL;
     while(root||!s.empty()){
        if(root){
            s.push(root);
            root=root->left;
        }else{
            root=s.top();
            s.pop();
            if(pre==NULL){
                head=root;
            }else{
                pre->right=root;
                root->left=pre;

            }
            pre=root;
            root=root->right;
        }
     }
     pre->right=head;
     head->left=pre;
     return head;
    }

树的子结构

判断B是不是A的子结构

bool helper(TreeNode* A, TreeNode* B) {
        if (A == NULL || B == NULL) {
            return B == NULL ? true : false;
        }
        if (A->val != B->val) {
            return false;
        }
        return helper(A->left, B->left) && helper(A->right, B->right);
    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (A == NULL || B == NULL) {
            return false;
        }
        return helper(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B);
    }

二叉树的最近公共祖先

后序遍历子树，找到p，q

1 p, q 分别位于 x 的左子树和右子树；return root;
2 p, q 都在 x 的左子树. return left
3 p, q 都在 x 的右子树 return right

 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL)return NULL;
        if(root->val==p->val||root->val==q->val)
            return root;
        TreeNode* left=lowestCommonAncestor( root->left,  p,  q);
        TreeNode* right=lowestCommonAncestor( root->right,  p,  q);
        if(left&&right)return root;
        else if(left) return left;
        else if(right) return right;
        return NULL;
    }

1122344