[LeetCode] Binary Tree Paths - 二叉树基础系列题目

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //创建空容器 对象类型为string类
    vector<string> result;
    void getPaths(TreeNode* node,string path) {
        if(node->left==NULL && node->right==NULL) { //左右子树为空 路径寻找完成 增加至数组中
            result.push_back(path);
        }
        if(node->left!=NULL) { //递归遍历左子树 当前路径添加左孩子结点
            getPaths(node->left,path+"->"+to_string(node->left->val));
        }
        if(node->right!=NULL) { //递归遍历右子树
            getPaths(node->right,path+"->"+to_string(node->right->val));
        }
    }
    
    //获取二叉树路径
    vector<string> binaryTreePaths(TreeNode* root) {
        if(root==NULL)
            return result;
        getPaths(root, to_string(root->val)); //to_string整数转换为字符串
        return result;
    }
};

public class Solution {
    
    List<String> res = new ArrayList<String>();
    
    public List<String> binaryTreePaths(TreeNode root) {
        if(root != null) findPaths(root,String.valueOf(root.val));
        return res;
    }
    
    private void findPaths(TreeNode n, String path){
        if(n.left == null && n.right == null) res.add(path);
        if(n.left != null) findPaths(n.left, path+"->"+n.left.val);
        if(n.right != null) findPaths(n.right, path+"->"+n.right.val);
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
//递归方法
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(p==NULL&&q==NULL)
        return true;
    else if( (p!=NULL&&q==NULL) || (p==NULL&&q!=NULL) )
        return false;
    else
    {
        if(p->val != q->val)
            return false;
        else
            return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
 //比较左右结点
 bool isSameNode(struct TreeNode* L, struct TreeNode* R) {
     if(L==NULL&&R==NULL) {
         return true;
     }
     else if((L!=NULL&&R==NULL) || (L==NULL&&R!=NULL)) { //其中一个为空
         return false;
     }
     else if(L->val!=R->val) {
         return false;
     }
     else {
         return isSameNode(L->left,R->right) && isSameNode(L->right,R->left);
     }
 }
 //判断二叉树是否为镜像对称
bool isSymmetric(struct TreeNode* root) {
    if(!root)
        return true;
    else {
        return isSameNode(root->left,root->right);
    }
}

class Solution {  
public:  
    bool isSymmetric (TreeNode* root) {  
        if (!root) return true;  
        stack<TreeNode*> s;  
        s.push(root->left);  
        s.push(root->right);  
        while (!s.empty ()) {  
            auto p = s.top (); s.pop();  
            auto q = s.top (); s.pop();  
            if (!p && !q) continue;  
            if (!p || !q) return false;  
            if (p->val != q->val) return false;  
            s.push(p->left);  
            s.push(q->right);  
            s.push(p->right);  
            s.push(q->left);  
        }  
        return true;  
    }  
};